[CEOI 2023] Balance

Luogu

IDLGP9731

Time2000ms

Memory1024MB

DifficultyP6

2023Special JudgeO2优化CEOI（中欧）欧拉回路构造

由于黑客对评测机的攻击，组委会决定重测所有提交记录。有 $N$ 台评测机，$T$ 个题目（编号为 $1, 2, \cdots, T$）。组委会已经确定，每台评测机要评测哪些提交（数目相同，都是 $S$ 个提交，保证 $S$ 是 $2$ 的整数次幂）。在接下来的 $S$ 分钟内，每分钟每台评测机会评测一个提交。每个提交都会提交至某个题目。由于存数据的机器太脆弱了，所以要求，对于所有题目和任意两个时刻，在这两个时刻，这个题的被评测的提交的数量之差不超过 $1$。请构造一组方案，使得满足上面的条件。 ## Input 第一行输入 $N, S, T$。接下来 $N$ 行，每行输入 $S$ 个整数，表示这个评测机被分配到的提交的题目编号。 ## Output 输出 $N$ 行，每行 $S$ 个数，表示这个评测机按顺序要评测的提交的题目编号。可以证明，一定存在一组解。 [samples] ## Background 翻译自 CEOI2023 Day1 T3 [Balance](https://www.ceoi2023.de/wp-content/uploads/2023/09/3-balance.pdf)。 ## Note 保证存在正整数 $k$ 使得 $S = 2 ^ k$，$1 \le N, S, T \le 10 ^ 5$，$NS \le 5 \times 10 ^ 5$。 - Subtask 1（$10$ 分）：$S = 2$ 且 $N, T \le 20$。 - Subtask 2（$15 + 5 + 5$ 分）：$S = 2$。 - Subtask 3（$15 + 5 + 5$ 分）：$NS \le 10 ^ 4$。 - Subtask 4（$20 + 10 + 10$ 分）：没有其它限制。对于后三个子任务，存在部分分（对应括号中的分数）： - 第一个数表示如果能解决满足 $T \le N$ 且对于每个题目的提交数量均整除 $S$ 时的所有测试点能得到的分数。 - 第二个数表示如果能解决满足 $T \le N$ 时的所有测试点能多得到的分数。 - 第三个数表示如果解决了整个 Subtask 时能多得到的分数。在洛谷上，本题分为 $10$ 个子任务。对于原来的后三个 Subtask，在本题中分别按顺序分为三个子任务（如原 Subtask 3 就是子任务 $5, 6, 7$），有依赖关系。

Samples

Input #1

Output #1

2 1
3 2
2 3

Input #2

Output #2

2 2 2 3
3 2 3 2
2 3 2 2

API Response (JSON)

{
  "problem": {
    "name": "[CEOI 2023] Balance",
    "description": {
      "content": "由于黑客对评测机的攻击，组委会决定重测所有提交记录。 有 $N$ 台评测机，$T$ 个题目（编号为 $1, 2, \\cdots, T$）。组委会已经确定，每台评测机要评测哪些提交（数目相同，都是 $S$ 个提交，保证 $S$ 是 $2$ 的整数次幂）。在接下来的 $S$ 分钟内，每分钟每台评测机会评测一个提交。 每个提交都会提交至某个题目。由于存数据的机器太脆弱了，所以要求，对于所有题目和任意",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9731"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "由于黑客对评测机的攻击，组委会决定重测所有提交记录。\n\n有 $N$ 台评测机，$T$ 个题目（编号为 $1, 2, \\cdots, T$）。组委会已经确定，每台评测机要评测哪些提交（数目相同，都是 $S$ 个提交，保证 $S$ 是 $2$ 的整数次幂）。在接下来的 $S$ 分钟内，每分钟每台评测机会评测一个提交。\n\n每个提交都会提交至某个题目。由于存数据的机器太脆弱了，所以要求，对于所有题目和任意...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments