COI '20 #4 MalnaRISC

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

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. Malnar 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_jR_i\ R_j – swaps the values in registers R_iR_i and R_jR_j if R_i > R_jR_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_NR_1, R_2, \dots, R_N contain some integers. Write an efficient code in assembly that sorts these values in non-descending order.

Note: The sample input is not in the test data. Also for each subtask, your solution will be validated against a series of sequences of RR as checking against all permutations would not be feasible. The series of sequences will be the same each time you submit.

Input Specification

The only line contains an integer NN from the task description.

Output Specification

Output an integer tt into the first line denoting the execution time of your program (in nanoseconds).

In the next tt lines output the assembly code that sorts the values in the NN 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_jR_i\ R_j" (1 \le i, j \le N)(1 \le i, j \le N), and the instructions in a single line need to be separated by a single space character.

Scoring

Subtask NN t_1t_1 t_2t_2 t_3t_3 Points
11 88 2828 1212 66 1010
22 1313 7878 2222 1010 1010
33 1616 120120 2828 1010 1010
44 3232 496496 6060 1515 1010
55 5353 13781378 102102 2121 1010
66 6464 20162016 124124 2121 1010
77 7373 26282628 142142 2828 1010
88 8282 33213321 160160 2828 1010
99 9191 40954095 178178 2929 1010
1010 100100 49504950 196196 3030 1010

If you have outputted a correct program on some subtask that correctly sorts the values in registers in tt nanoseconds, your solutions will be scored according to the following expression:

\displaystyle \text{points}(t) = \begin{cases}
0 & t > t_1\\
1+\dfrac{2}{t-t_2} & t_1 \ge t > t_2\\
3+\dfrac{7(t_2-t+1)}{t_2-t_3} & t_2 \ge t > t_3\\
10 & t_3 \ge t
\end{cases}\displaystyle \text{points}(t) = \begin{cases}
0 & t > t_1\\
1+\dfrac{2}{t-t_2} & t_1 \ge t > t_2\\
3+\dfrac{7(t_2-t+1)}{t_2-t_3} & t_2 \ge t > t_3\\
10 & t_3 \ge t
\end{cases}

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.

Sample Input 1

2

Sample Output 1

1
CMPSWP R1 R2

Sample Input 2

3

Sample Output 2

3
CMPSWP R1 R2
CMPSWP R1 R3
CMPSWP R2 R3

Sample Input 3

4

Sample Output 3

4
CMPSWP R1 R3
CMPSWP R2 R4
CMPSWP R1 R2 CMPSWP R3 R4
CMPSWP R2 R3

Comments

There are no comments at the moment.