시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 29 | 6 | 5 | 33.333% |
It’s early in the morning and Croatian IOI team is starting to assemble at the Zagreb airport. The trip is long with the final destination being Singapore with a layover in Amsterdam. Mr. Malar drank the last drop of his grapefruit-based beverage and ordered the team to proceed to the gate. As it usually happens, he disappeared after the security check and somehow managed to show up just a few minutes before boarding.
Olympian 1: Where were you?! I swear you’re gonna miss the next flight if you keep doing this.
Mr. Malnar: It’s not my fault this time, the security wouldn’t let me through. They thought I might be a terrorist.
Olympian 2: A terrorist?! You wouldn’t hurt a fly. What happened?
Mr. Malnar: Ah, they found MalnaRISC (Reduced Instruction Set Computer) and refused to believe me that I am capable of building my own processor. They let me go once I explained how efficient it is at sorting integers.
Olympian 3: I also wouldn’t believe you. As a matter of fact, I still don’t. What makes your processor so interesting?
Mr. Malnar: You are members of our national IOI team, I shouldn’t need to explain anything to you. Here is the documentation, figure it out yourselves.
Olympian 4: Give that to me, I’ll solve this year’s COI on it using the assembly.
The assembly language for MalnaRISC contains a single instruction:
CMPSWP
$R_i$ $R_j$ – swaps the values in registers $R_i$ and $R_j$ if $R_i > R_j$ holds.What’s special about MalnaRISC is that all instructions written in the same line will execute in parallel during a single nanosecond. Naturally, each register can only be used at most once as an argument in a single line.
It is known that registers $R_1, R_2, \dots , R_N$ contain some integers. Write an efficient code in assembly that sorts these values in non-descending order.
The only line contains an integer $N$ from the task description.
Output an integer $t$ into the first line denoting the execution time of your program (in nanoseconds).
In the next $t$ lines output the assembly code that sorts the values in the $N$ registers. Each line should contain at least one instruction, and each register should only be mentioned once in a single line. Each instruction needs to be of the form "CMPSWP
$R_i$ $R_j$" ($1 \le i, j \le N$), and the instructions in a single line need to be separated by a single space character.
If you have outputted a correct program on some subtask that correctly sorts the values in registers in $t$ nanoseconds, your solutions will be scored according to the following expression: $$points(t) = \begin{cases} 0 & t > t_1 \\ 100 + \frac{200}{t-t_2} & t_1 \ge t > t_2 \\ 300 + \frac{700(t_2-t+1)}{t_2-t_3} & t_2 \ge t > t_3 \\ 1000 & t_3 \ge t\end{cases}$$
The points for each subtask will be rounded down to nearest integer.
번호 | 배점 | 제한 |
---|---|---|
1 | 1000 | $N = 8, t_1 = 28, t_2 = 12, t_3 = 6$ |
2 | 1000 | $N = 13, t_1 = 78, t_2 = 22, t_3 = 10$ |
3 | 1000 | $N = 16, t_1 = 120, t_2 = 28, t_3 = 10$ |
4 | 1000 | $N = 32, t_1 = 496, t_2 = 60, t_3 = 15$ |
5 | 1000 | $N = 53, t_1 = 1378, t_2 = 102, t_3 = 21$ |
6 | 1000 | $N = 64, t_1 = 2016, t_2 = 124, t_3 = 21$ |
7 | 1000 | $N = 73, t_1 = 2628, t_2 = 142, t_3 = 28$ |
8 | 1000 | $N = 82, t_1 = 3321, t_2 = 160, t_3 = 28$ |
9 | 1000 | $N = 91, t_1 = 4095, t_2 = 178, t_3 = 29$ |
10 | 1000 | $N = 100, t_1 = 4950, t_2 = 196, t_3 = 30$ |
2
1 CMPSWP R1 R2
3
3 CMPSWP R1 R2 CMPSWP R1 R3 CMPSWP R2 R3
4
4 CMPSWP R1 R3 CMPSWP R2 R4 CMPSWP R1 R2 CMPSWP R3 R4 CMPSWP R2 R3
Olympiad > Croatian Highschool Competitions in Informatics > 2021 > Croatian Olympiad in Informatics 2021 4번