B. Kozak Vus and Programming
Kozak has a favorite robot named Atlas, which he played with a lot during his childhood. Recently, Vus realized he had never tried programming the robot for different tasks, so he started reading the manual. He discovered that Atlas has 40 registers, each numbered starting from one, and each register contains 64 bits. This means each register is made up of 64 zeros and ones.
Vus learned that the robot can be programmed using seven specific commands that perform operations on these registers. For simplicity, we'll refer to register i as the register with the number i, and a[i] as the number stored in the i-th register.
setValue(i, j) — Replace the contents of register i with those of register j. This means each bit in register i is replaced by the corresponding bit in register j, effectively performing the operation
a[i]=a[j].setXor(i, j, k) — Replace the contents of register i with the bitwise XOR of registers j and k. Each bit in register i is replaced by the XOR of the corresponding bits in registers j and k.
setAnd(i, j, k) — Replace the contents of register i with the bitwise AND of registers j and k. Each bit in register i is replaced by the AND of the corresponding bits in registers j and k.
setOr(i, j, k) — Replace the contents of register i with the bitwise OR of registers j and k. Each bit in register i is replaced by the OR of the corresponding bits in registers j and k.
shiftLeft(i, x) — Shift all bits in register i x positions to the left. The shift operation is explained below.
shiftRight(i, x) — Shift all bits in register i x positions to the right. The shift operation is explained below.
setNot(i, j) — Replace the contents of register i with the inverted contents of register j. Each bit in register i is set to 1 if the corresponding bit in register j is 0, and set to 0 if the corresponding bit in register j is 1.
The XOR operation results in 0 if the bits are the same, and 1 if they are different. The AND operation results in 1 if both bits are 1, and 0 if at least one bit is 0. The OR operation results in 0 if both bits are 0, and 1 if at least one bit is 1.
Shifting a register x positions to the left results in a register where each bit is equal to the bit that was x positions to the right in the original register, with 0 filling any positions that do not have a corresponding bit. Shifting a register x positions to the right results in a register where each bit is equal to the bit that was x positions to the left in the original register, with 0 filling any positions that do not have a corresponding bit.
After reading the manual, Kozak Vus came up with six interesting tasks. He realized that to program the robot for a specific task, he only needs to input a sequence of commands that will solve the task. Suppose t is the number of commands executed for a certain task.
Here are the tasks:
Subtask 1: (up to 6 points) The number x is stored in register 1. All other registers are filled with 0s. Let the number y be 1 if x is even, and 0 if x is odd. The task is to ensure that after executing the operations, the number y is stored in register 2.
Subtask 2: (up to 10 points) The number x is stored in register 1, and the number y is stored in register 2. All other registers are filled with 0s. Let z = x + y. The task is to ensure that after executing the operations, the number z is stored in register 3. If the binary representation of z requires more than 64 bits, only the first 64 bits should be stored in register 3.
Subtask 3: (up to 13 points) The number x is stored in register 1. Let y be the number of ones in the binary representation of x. After executing the operations, y should be stored in register 2.
Subtask 4: (up to 23 points) Two different numbers x and y are stored in registers 1 and 2, respectively. If x > y, then a = 0 and b = 1; if y > x, then b = 0 and a = 1. The task is to ensure that after executing the operations, the numbers a and b are stored in registers 3 and 4, respectively.
Subtask 5: (up to 18 points) The number x is stored in register 1. Let y be the number of ones in the binary representation of x. After executing the operations, the number 2^y - 1 should be stored in register 1.
Subtask 6: (up to 30 points) Let a be an array containing 9 non-negative distinct integers. For each i from 1 to 9, the number a[i] is stored in the i-th register. Let b be the sorted array a in ascending order. After executing the operations, for each i from 1 to 9, the number b[i] should be stored in the i-th register.
If no initial value is specified for a register, it is filled with zeros at the start. All numbers are between 0 and 2^64 - 1.
Kozak Vus knows the number of commands needed to solve each task but doesn't know which commands to use, so he seeks your help. Your task is to find a sequence of commands that will solve each task for any possible input data.
Note that you can execute no more than 10^5 commands. Exceeding this limit will result in 0 points and a Wrong Answer verdict. Executing an incorrect request will result in 0 points and a Runtime Error verdict. The result of your solution in each subtask will be the registers where the solutions should be recorded. Any numbers can be in all other registers.
Interaction
For each subtask, you need to implement a separate function:
void solve(int n), where n is the subtask number.
This function does not take any parameters and does not return anything.
You can use the following functions:
void setValue(integer i, integer j): Assigns the value of register j (1 ⩽ j ⩽ 40) to register i (1 ⩽ i ⩽ 40).
void setXor(integer i, integer j, integer k): Assigns the value of the XOR operation of registers j (1 ⩽ j ⩽ 40) and k (1 ⩽ k ⩽ 40) to register i (1 ⩽ i ⩽ 40).
void setAnd(integer i, integer j, integer k): Assigns the value of the AND operation of registers j (1 ⩽ j ⩽ 40) and k (1 ⩽ k ⩽ 40) to register i (1 ⩽ i ⩽ 40).
void setOr(integer i, integer j, integer k): Assigns the value of the OR operation of registers j (1 ⩽ j ⩽ 40) and k (1 ⩽ k ⩽ 40) to register i (1 ⩽ i ⩽ 40).
void shiftLeft(integer i, integer x): Performs a shift of register i (1 ⩽ i ⩽ 40) by x (0 ⩽ x ⩽ 64) positions to the left.
void shiftRight(integer i, integer x): Performs a shift of register i (1 ⩽ i ⩽ 40) by x (0 ⩽ x ⩽ 64) positions to the right.
void setNot(integer i, integer j): Assigns the value of the inverted register j (1 ⩽ j ⩽ 40) to register i (1 ⩽ i ⩽ 40).
Example:
Suppose the number 6 is stored in register 1, and the number 3 is stored in register 2. If we execute the following commands:
setValue(3, 1)
setXor(4, 1, 2)
setAnd(5, 1, 2)
setOr(6, 2, 1)
shiftLeft(2, 3)
shiftRight(1, 2)
setNot(7, 2)
Then the first seven numbers of the array will look like this: [1, 24, 6, 5, 2, 7, 18446744073709551591].