#include "prison.h"
#include <vector>
std::vector<std::vector<int>> devise_strategy(int N) {
std::vector<int> operation;
std::vector<std::vector<int>> res;
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 {
operation.push_back(2);
//printf(" if I see %d coins, I write %d\n", i, val+2);
}
}
// steady state
int offset = 0;
for (int j = 11; j >= 0; 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 = 3 + 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(bag == 0 ? -2 : - 1);
//printf(" if I see %d coins, I write B is heavier\n", i);
}
else {
operation.push_back(bag == 0 ? -1 : -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;
}
// got 0
operation.push_back(1);
for (int i = 1; i <= N; i++) {
if ((i & 0x1) == 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 1
//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 & 0x1) == 1) {
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);
operation.push_back(-2);
}
}
res.push_back(operation);
operation.erase(operation.begin(), operation.end());
return 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 >= 2; 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 >> 2) & 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 & 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);
operation.push_back(-2);
}
}
res.push_back(operation);
operation.erase(operation.begin(), operation.end());
return res;
}
}
