| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 105 | 17 | 16 | 17.582% |
A hectic first competition day has passed… While the Scientific Committee narrowly fought off the hacking attack on the grading server, they fear that it affected the scoring of the submissions. There is only one option: all submissions have to be rejudged!
The grading server has $N$ processor cores. The committee has already assigned a list of $S$ submissions to each core, where each submission is to one of the $T$ tasks of the competition (numbered 1,ドル \dots , T$). The committee made sure that $S$ is a power of two.* Now, in the next $S$ minutes, each core will evaluate exactly one submission from its list per minute.
Unfortunately, the database containing the task data is quite fragile and could crash if the number of simultaneous requests for a single task’s data varies widely. Therefore, the committee wants to order the submissions of each core in such a way that, during the rejudging, the maximum and minimum number of simultaneously evaluated submissions for any single task differ by at most one.
Write a program which computes such an ordered assignment of the submissions to the cores.
* Due to a bug,† the judging system would crash otherwise, taking down all firewalls and potentially exposing sensitive information!
† You had one job, Wolfgang!
The first line of input contains the three integers $N,ドル $S,ドル and $T$ described above.
Then, $N$ lines follow describing the submissions assigned to the cores. The $i$-th of these lines contains $S$ integers $t_1 , \dots , t_S$ (1ドル ≤ t_j ≤ T$), meaning that the $i$-th core is assigned submissions to the tasks $t_1 , \dots , t_S$ respectively.
Your program should output $N$ lines that describe an ordered assignment of the submissions to the cores such that the maximum and minimum number of simultaneously evaluated submissions for any single task differ by at most one: The $i$-th of these lines should contain $S$ integers $r_1 , \dots , r_S,ドル meaning that the $i$-th core evaluates a submission to task $r_j$ during the $j$-th minute. It is guaranteed that such an assignment exists for each testcase.
We always have that $S = 2^k$ for some positive integer $k,ドル 1ドル ≤ N, S, T ≤ 100,000円$ and $N \cdot S ≤ 500,000円$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $S = 2$ and $N, T ≤ 20$ |
| 2 | 25 | $S = 2$ |
| 3 | 25 | $N \cdot S ≤ 10,000円$ |
| 4 | 40 | No further constraints. |
3 2 3 1 2 2 3 2 3
2 1 3 2 2 3
3 4 3 2 3 2 2 2 3 3 2 2 2 3 2
2 2 2 3 3 2 3 2 2 3 2 2
In the output of the first example, the difference between the maximum and the minimum number of simultaneously evaluated submissions is one for tasks 1ドル$ and 2ドル$ and zero for task 3ドル$. On the other hand, ordering the submissions as in the input would not have constituted a valid output because the difference between the maximum and the minimum number of simultaneously evaluations submissions for task 3ドル$ is two.
In the output of the second example, the difference between the maximum and the minimum number of simultaneously evaluated submissions is zero for all three tasks.