#include "prison.h"
#include <vector>
std::vector<std::vector<int>> devise_strategy(int N) {
std::vector<int> operation;
std::vector<std::vector<int>> res;
// first 5 operations
operation.push_back(0);
int mask = 1 << 12;
//printf(" I am prisoner %d open bag A\n", res.size() + 1);
for (int i = 1; i <= N; i++) {
if ((i & mask) == mask) {
operation.push_back(1);
//printf(" if I see %d coins, I write %d\n", i, 1);
}
else {
int val = (i >> 10) & 0x3;
operation.push_back(val+2);
//printf(" if I see %d coins, I write %d\n", i, val+2);
}
}
res.push_back(operation);
operation.erase(operation.begin(), operation.end());
// if a prisoner gets 1
operation.push_back(1);
//printf(" I am prisoner %d open bag B\n", res.size() + 1);
for (int i = 1; i <= N; i++) {
if ((i & mask) == mask) {
int myBit = (i >> 9) & 0x1;
int opcode = 6 + myBit;
operation.push_back(opcode);
//printf(" if I see %d coins, I write %d\n", i, opcode);
}
else {
operation.push_back(-2);
//printf(" if I see %d coins, I write A is heavier\n", i);
}
}
res.push_back(operation);
operation.erase(operation.begin(), operation.end());
// if a prisoner gets 2-5
for (int j = 2; j <= 5; j++) {
//printf(" I am prisoner %d open bag B\n", res.size() + 1);
operation.push_back(1);
for (int i = 1; i <= N; i++) {
int bitsB = (i >> 10) & 0x3;
int bitsA = j - 2;
if (bitsA < bitsB) {
operation.push_back(-1);
//printf(" if I see %d coins, I write B is heavier\n", i);
}
else if (bitsB < bitsA) {
operation.push_back(-2);
//printf(" if I see %d coins, I write A is heavier\n", i);
}
else {
int myBit = (i >> 9) & 0x1;
int opcode = 6 + myBit;
operation.push_back(opcode);
//printf(" if I see %d coins, I write %d\n", i, opcode);
}
}
res.push_back(operation);
operation.erase(operation.begin(), operation.end());
}
// steady state
int offset = 0;
for (int j = 8; j >= 3; j--) {
int bag = j & 0x1;
for (int k = 0; k < 2; k++) {
//printf(" I am prisoner %d open bag %s\n", res.size() + 1, bag == 0 ? "A" : "B");
operation.push_back(bag);
for (int i = 1; i <= N; i++) {
int checkBit = (i >> (j + 1)) & 0x1;
int passBit = (i >> j) & 0x1;
if (checkBit == k) {
int opcode = 8 + offset * 2 + passBit;
operation.push_back(opcode);
//printf(" if I see %d coins, I write %d\n", i, opcode);
}
else {
if (checkBit == 1) {
operation.push_back(-1);
//printf(" if I see %d coins, I write B is heavier\n", i);
}
else {
operation.push_back(-2);
//printf(" if I see %d coins, I write A is heavier\n", i);
}
}
}
res.push_back(operation);
operation.erase(operation.begin(), operation.end());
}
++offset;
}
for (int k = 0; k < 2; k++) {
operation.push_back(0);
//printf(" (pass last 2 a) I am prisoner %d open bag A\n", res.size() + 1);
for (int i = 1; i <= N; i++) {
int checkBit = (i >> 3) & 0x1;
if (checkBit < k) {
//printf(" if I see %d coins, I write A is heavier\n", i);
operation.push_back(-2);
}
else if (checkBit > k) {
//printf(" if I see %d coins, I write B is heavier\n", i);
operation.push_back(-1);
}
else {
int myBits = (i >> 2) & 0x3;
if (myBits == 0) {
operation.push_back(-1);
//printf(" if I see %d coins, I write B is heavier\n", i);
}
else if (myBits == 3) {
operation.push_back(-2);
//printf(" if I see %d coins, I write A is heavier\n", i);
}
else if (myBits == 1) {
operation.push_back(8 + offset * 2);
//printf(" if I see %d coins, I write %d\n", i, 8 + offset * 2);
}
else if (myBits == 2) {
operation.push_back(8 + offset * 2 + 1);
//printf(" if I see %d coins, I write %d\n", i, 8 + offset * 2 + 1);
}
}
}
res.push_back(operation);
operation.erase(operation.begin(), operation.end());
}
// last 2
// got 1, he has 01 or 00
//printf(" (check last 2 a) I am prisoner %d open bag B\n", res.size() + 1);
operation.push_back(1);
for (int i = 1; i <= N; i++) {
if ((i & 0x3) >= 1) {
operation.push_back(-1);
//printf(" if I see %d coins, I write B is heavier\n", i);
}
else {
operation.push_back(-2);
//printf(" if I see %d coins, I write A is heavier\n", i);
}
}
res.push_back(operation);
operation.erase(operation.begin(), operation.end());
// got 2
//printf("(check last 2 b) I am prisoner %d open bag B\n", res.size() + 1);
operation.push_back(1);
for (int i = 1; i <= N; i++) {
if ((i & 0x3) >= 2) {
operation.push_back(-1);
//printf(" if I see %d coins, I write B is heavier\n", i);
}
else {
//printf(" if I see %d coins, I write A is heavier\n", i);
}
}
res.push_back(operation);
operation.erase(operation.begin(), operation.end());
return res;
}
