#include <bits/stdc++.h>
using namespace std;
// Function declarations provided by grader
void append_move(int t, int y);
void append_store(int t, vector<int> v);
void append_and(int t, int x, int y);
void append_or(int t, int x, int y);
void append_xor(int t, int x, int y);
void append_not(int t, int x);
void append_left(int t, int x, int p);
void append_right(int t, int x, int p);
void append_add(int t, int x, int y);
// THIS is what you implement:
void construct_instructions(int n, int k, int q, int w) {
// n = number of integers
// k = bits per integer
// q = max operations
// w = total bits (2000)
// Step 1: Load numbers into separate registers
// Input: r[0] contains all n numbers packed as bits [0:k), [k:2k), ...
for(int i = 0; i < n; i++) {
if(i > 0) {
append_right(10 + i, 0, i * k); // Extract i-th number
}
}
// Step 2: Bubble sort using bitwise comparison
for(int i = 0; i < n && i < q; i++) {
for(int j = 0; j < n - i - 1 && j + i < q; j++) {
int idx1 = (i == 0) ? 0 : (10 + j);
int idx2 = (j == 0 && i == 0) ? 1 : (10 + j + 1);
int temp = 20 + j;
// Compare: if r[idx1] > r[idx2], swap
// Use XOR to compute if different: a XOR b = 0 if equal
append_xor(temp, idx1, idx2);
// For actual comparison, use: subtract and check sign
// diff = a - b
append_not(temp + 1, idx2);
append_add(temp + 1, idx1, temp + 1);
append_add(temp + 1, temp + 1, 1);
// If diff is negative (top bit set), then idx1 < idx2 (already in order)
// If diff is positive, swap needed
append_right(temp + 2, temp + 1, k - 1); // Extract sign bit
}
}
// Step 3: Reconstruct sorted array into r[0]
append_store(0, vector<int>(n)); // Store all zeros first
for(int i = 0; i < n; i++) {
int src = (i == 0) ? 0 : (10 + i);
append_left(0, src, i * k); // Reconstruct into r[0]
}
}
