Croatian Olympiad in Informatics
April \(25^{th}\) 2021
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 grapefru\(it-ba\)sed 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@@RISE_MATH_BLOCK_0@@j\) – swaps the values in registers \(R@@RISE_MATH_BLOCK_1@@j\) if \(R@@RISE_MATH_BLOCK_2@@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}\), . . . , \(R_{N}\) contain some integers. Write an efficient code in assembly that
sorts these values in n\(on-de\)scending order.

Subtask 1 (8 points): —

Subtask 28 (12 points): —

Subtask 6 (10 points): —

Subtask 2 (13 points): —

Subtask 78 (22 points): —

Subtask 10 (10 points): —

Subtask 3 (16 points): —

Subtask 120 (28 points): —

Subtask 10 (10 points): —

Subtask 4 (32 points): —

Subtask 496 (60 points): —

Subtask 15 (10 points): —

Subtask 5 (53 points): —

Subtask 1378 (102 points): —

Subtask 21 (10 points): —

Subtask 6 (64 points): —

Subtask 2016 (124 points): —

Subtask 21 (10 points): —

Subtask 7 (73 points): —

Subtask 2628 (142 points): —

Subtask 28 (10 points): —

Subtask 8 (82 points): —

Subtask 3321 (160 points): —

Subtask 28 (10 points): —

Subtask 9 (91 points): —

Subtask 4095 (178 points): —

Subtask 29 (10 points): —

Subtask 10 (100 points): —

Subtask 4950 (196 points): —

Subtask 30 (10 points): 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\)) =          0 \(t > t@@RISE_MATH_BLOCK_0@@1 \ge t > t\)2 3 + ^{7(}{2}{t} \(t\)\(2 - t\)3 \(t_{2} \ge t > t_{3}\) 10 \(t_{3} \ge t\) The points for each subtask will be rounded to two decimal places. The total scored is obtained by summing these points and rounding that sum in the same manner.

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@@RISE_MATH_BLOCK_0@@j\)" (\(1 \le i\), \(j \le N\)), and the instructions in a single line
need to be separated by a single space character.
6 od 7
Croatian Olympiad in Informatics
April \(25^{th}\) 2021

생성자가 기록되지 않았습니다.

출처 COCI 2020/2021 Olympiad