#include <bits/stdc++.h>
#include "registers.h"
using namespace std;
const int b = 2000;
const int m = 100;
vector<bitset<b>> r(m);
int cnt = 0;
int so_far = 0;
void Move(int t, int y) {
r[t] = r[y];
so_far++;
}
int Store(vector<bool> v) {
so_far++;
int t = cnt++;
assert(int(v.size()) == b);
append_store(t, v);
for (int i = 0; i < b; i++) r[t][i] = v[i];
return t;
}
int And(int x, int y) {
so_far++;
int t = cnt++;
append_and(t, x, y);
r[t] = r[x] & r[y];
return t;
}
int Or(int x, int y) {
so_far++;
int t = cnt++;
append_or(t, x, y);
r[t] = r[x] | r[y];
return t;
}
int Xor(int x, int y) {
so_far++;
int t = cnt++;
append_xor(t, x, y);
r[t] = r[x] ^ r[y];
return t;
}
int Not(int x) {
so_far++;
int t = cnt++;
append_not(t, x);
for (int i = 0; i < b; i++) r[t][i] = r[x][i] ? 0 : 1;
return t;
}
int Shift_left(int x, int p) {
so_far++;
int t = cnt++;
append_left(t, x, p);
r[t] = r[x] << p;
return t;
}
int Shift_right(int x, int p) {
so_far++;
int t = cnt++;
append_right(t, x, p);
r[t] = r[x] >> p;
return t;
}
int Add(int x, int y) {
so_far++;
int t = cnt++;
append_add(t, x, y);
int carries = 0;
for (int i = 0; i < b; i++) {
int sum = r[x][i] + r[y][i] + carries;
r[t][i] = sum % 2;
carries = sum / 2;
}
return t;
}
struct Bitset {
int id = -1;
Bitset(int _id) : id(_id) {};
Bitset operator-() const { return Bitset(Not(id)); };
Bitset operator>>(int p) { return Bitset(Shift_right(id, p)); };
Bitset operator<<(int p) { return Bitset(Shift_left(id, p)); };
void operator=(const Bitset &a) { Move(id, a.id); };
};
Bitset operator+(const Bitset &lhs, const Bitset &rhs) { return Bitset(Add(lhs.id, rhs.id)) ;}
Bitset operator^(const Bitset &lhs, const Bitset &rhs) { return Bitset(Xor(lhs.id, rhs.id)) ;}
Bitset operator|(const Bitset &lhs, const Bitset &rhs) { return Bitset(Or(lhs.id, rhs.id)) ;}
Bitset operator&(const Bitset &lhs, const Bitset &rhs) { return Bitset(And(lhs.id, rhs.id)) ;}
Bitset Store(const function<bool(const int&)> &f) {
vector<bool> bits(b);
for (int i = 0; i < b; i++) bits[i] = f(i);
return Bitset(Store(bits));
}
void construct_instructions(int s, int n, int k, int q) {
Bitset a = Bitset(0);
cnt++;
Bitset Full = Store([&](int i) {
return true;
});
Bitset One = Store([&](int i) {
return i == 0;
});
int reset_register = cnt;
auto Lesser_greater = [&](Bitset Even_skipped_blocks, Bitset Odd_skipped_blocks, int total_blocks) {
assert(total_blocks & 1);
Bitset Full_even_indexes = Store([&](int i) {
int block_id = i / k;
if (block_id >= total_blocks) return false;
if (block_id & 1) return false;
return true;
});
Bitset Header_remainder_even_blocks = Store([&](int i) {
int block_id = i / k;
if (block_id >= total_blocks + 1) return false;
if (i % (2 * k) == k) return true;
return false;
});
Bitset Even_plus_full_minus_odd = Even_skipped_blocks + (Full_even_indexes ^ Odd_skipped_blocks);
Bitset Greater_even_blocks_head = Even_plus_full_minus_odd & Header_remainder_even_blocks;
Bitset Full_greater_even_blocks = Greater_even_blocks_head + (Full ^ Greater_even_blocks_head >> k) + One;
Bitset Full_not_less_odd_blocks = Full_greater_even_blocks ^ Full_even_indexes;
Bitset Greater_skipped = (Even_skipped_blocks & Full_greater_even_blocks) ^ (Odd_skipped_blocks & Full_not_less_odd_blocks);
Bitset Lesser_skipped = Even_skipped_blocks ^ Odd_skipped_blocks ^ Greater_skipped;
Bitset ret = Lesser_skipped ^ (Greater_skipped << k);
return ret;
};
auto E_O_switch = [&]() {
Bitset Even_skipped_blocks = a & Store([&](int i) {
if (i >= n * k) return false;
int block_id = i / k;
return block_id % 2 == 0;
});
Bitset Odd_skipped_blocks = (a & Store([&](int i) {
if (i >= n * k) return false;
int block_id = i / k;
return block_id % 2 == 1;
})) >> k;
int last_even_block_id = n - 1 - (n & 1 ^ 1);
int last_odd_block_id = n - 1 - (n & 1);
int total_block = last_even_block_id + 1;
if (last_odd_block_id != total_block) Odd_skipped_blocks = Odd_skipped_blocks | Store([&](int i) {
int L = (total_block - 1) * k, R = L + k - 1;
return L <= i && i <= R;
});
a = Lesser_greater(Even_skipped_blocks, Odd_skipped_blocks, total_block);
if (last_odd_block_id != total_block) a = a ^ Store([&](int i) {
int L = total_block * k + k, R = L + k - 1;
return L <= i && i <= R;
});
cnt = reset_register;
};
auto O_E_switch = [&]() {
if (n <= 2) return;
Bitset Even_skipped_blocks = (a & Store([&](int i) {
if (i >= n * k) return false;
int block_id = i / k;
return block_id % 2 == 0;
})) >> (k << 1);
Bitset Odd_skipped_blocks = (a & Store([&](int i) {
if (i >= n * k) return false;
int block_id = i / k;
return block_id % 2 == 1;
})) >> k;
int last_even_block_id = n - 1 - (n & 1 ^ 1);
int last_odd_block_id = n - 1 - (n & 1);
int total_block = last_odd_block_id;
if (last_even_block_id != total_block + 1) Even_skipped_blocks = Even_skipped_blocks | Store([&](int i) {
int L = (total_block - 1) * k, R = L + k - 1;
return L <= i && i <= R;
});
Bitset first_block = a & Store([&](int i) {
return i < k;
});
a = Lesser_greater(Odd_skipped_blocks, Even_skipped_blocks, total_block) << k | first_block;
if (last_odd_block_id != total_block) a = a ^ Store([&](int i) {
int L = (total_block + 1) * k + k, R = L + k - 1;
return L <= i && i <= R;
});
cnt = reset_register;
};
if (s == 1) {
int beg = 0;
int iter = n;
while (iter--) {
if (!beg & 1) {
E_O_switch();
} else {
O_E_switch();
}
beg ^= 1;
}
assert(so_far <= q);
} else {
Bitset Full_even_indexes = Store([&](int i) {
int block_id = i / k;
if (block_id & 1) return false;
return true;
});
Bitset Header_remainder_even_blocks = Store([&](int i) {
int block_id = i / k;
if (i % (2 * k) == k) return true;
return false;
});
auto Lesser = [&](Bitset Even_skipped_blocks, Bitset Odd_skipped_blocks) {
Bitset Even_plus_full_minus_odd = Even_skipped_blocks + (Full_even_indexes ^ Odd_skipped_blocks);
Bitset Greater_even_blocks_head = Even_plus_full_minus_odd & Header_remainder_even_blocks;
Bitset Full_greater_even_blocks = Greater_even_blocks_head + (Full ^ Greater_even_blocks_head >> k) + One;
Bitset Full_not_less_odd_blocks = Full_greater_even_blocks ^ Full_even_indexes;
Bitset Lesser_skipped = (Even_skipped_blocks & Full_not_less_odd_blocks) ^ (Odd_skipped_blocks & Full_greater_even_blocks);
return Lesser_skipped;
};
a = a | Store([&](int i) {
return n * k <= i;
});
Bitset Even_skipped_blocks = a & Full_even_indexes;
Bitset Odd_skipped_blocks = (a & Full_even_indexes << k) >> k;
Bitset Lesser_skipped = Lesser(Even_skipped_blocks, Odd_skipped_blocks);
int Log = 1;
while ((1 << Log) - 1 < n - 1) {
Lesser_skipped = Lesser(Lesser_skipped, Lesser_skipped >> (k << Log));
Log++;
}
a = Lesser_skipped;
}
}
