Problem Description

Translated from COI 2021 T4 “MalnaRISC”

You need to use the magical processor MalnaRISC to solve a well-known problem—sorting!

MalnaRISC supports only one instruction: CMPSWP $R_i$ $R_j$. Its meaning is: compare the values in $R_i$ and $R_j$, and if $R_i>R_j$, swap them.

The most powerful feature of MalnaRISC is that it can execute multiple different instructions written on the same line at the same time, as long as they do not conflict. That is, each register used as an argument to CMPSWP can appear at most once within the same line.

Now, please write a MalnaRISC program that sorts a sequence of length $N$ (in non-decreasing order). We will score your solution based on the length of your program.

Input Format

A single line containing one integer $N$.

Output Format

The first line contains an integer $t$, the length of your code.

The next $t$ lines each represent one line of your code.

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

Hint

Subtask	$N$	$t_1$	$t_2$	$t_3$	Score
$1$	$8$	$28$	$12$	$6$	$10$
$2$	$13$	$78$	$22$	$10$
$3$	$16$	$120$	$28$
$4$	$32$	$496$	$60$	$15$
$5$	$53$	$1378$	$102$	$21$
$6$	$64$	$2016$	$124$
$7$	$73$	$2628$	$142$	$28$
$8$	$82$	$3321$	$160$
$9$	$91$	$4095$	$178$	$29$
$10$	$100$	$4950$	$196$	$30$

If your correct code has $t$ lines, then you will receive the rounded score given by:

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

Translated by ChatGPT 5