#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define bv(x, i) (((x) & (1 << (i))) ? 1 : 0)
#define trit(x, i) (((x) / static_cast<int>(std::pow(3, (i)))) % 3)
using vi = vector<int>;
using vvi = vector<vi>;
struct State {
int bitID, id, bag;
// if id = 0, then current bag is A
// if id = 1, then current bag is B, and A[bit] = 0
// if id = 2, then current bag is B, and A[bit] = 1
};
const int BITS = 13, BASE = 2, STATES = 30;
vector<State> states;
int stateID[BITS][BASE];
// void build_state_table() {
// for (int i = BITS - 1; i >= 0; i--) {
// for (auto state : {0, 1, 2}) {
// stateID[i][state] = (int) states.size();
// states.push_back(State {i, state, i % 2});
// }
// }
// }
int transition(int current, int bagValue) {
if (current == 0) {
return bagValue & (1 << 12) ? 1 : 2;
} else if (current == 24) {
if (bagValue & (1 << 1)) return -2;
return bagValue & (1 << 0) ? -2 : -1;
} else if (current == 23) {
if (bagValue & (1 << 1)) return bagValue & (1 << 0) ? -2 : -1;
return -1;
}
int bit = 13 - ((current + 1) / 2);
bool pos = current % 2 == 1;
bool isa = bit % 2 == 1;
if (bit < 0) return -1;
if (((bagValue & (1 << bit)) > 0) == pos) {
if (current % 2 == 0) current--;
return current + ((bagValue & (1 << (bit - 1))) ? 2 : 3);
} else {
if (isa) {
return bagValue & (1 << bit) ? -2 : -1;
} else {
return bagValue & (1 << bit) ? -1 : -2;
}
}
return -1;
}
vi used(32, 0);
int test_strategy(int a, int b, vvi &strategy) {
int cnum = 0;
for (int i = 0; i < 500; i++) {
used[cnum]++;
int choose = strategy[cnum][0];
if (strategy[cnum][choose ? b : a] < 0) {
return -strategy[cnum][choose ? b : a];
} else {
cnum = strategy[cnum][choose ? b : a];
}
}
return 0;
}
vvi devise_strategy(int N) {
vvi s(STATES, vi(N+1, 0));
// build_state_table();
for (int i = 0; i < STATES; i++) {
// State cur = states[i];
int bit = 13 - ((i + 1) / 2);
s[i][0] = bit % 2 == 1 ? 0 : 1;
// s[i][0] = min(i, 1);
for (int j = 1; j <= N; j++) {
s[i][j] = transition(i, j);
}
}
// test_strategy(4096, 5000, s);
// for (int i = 1; i <= 5000; i++) {
// for (int j = 1; j <= 5000; j++) {
// if (i == j) continue;
// int ans = test_strategy(i, j, s);
// if (ans != (i < j ? 1 : 2)) {
// cout << "Fails on: " << i << ", " << j << "\n";
// break;
// }
// }
// }
// vi bits(STATES); iota(bits.begin(), bits.end(), 0);
// sort(bits.begin(), bits.end(), [&](const auto &a, const auto &b) {return used[a] < used[b];});
// for (int i = 0; i < STATES; i++) {
// cout << "Used state " << bits[i] << " " << used[bits[i]] << " times\n";
// }
// int mstate = 0; for (int i = 0; i < used.size(); i++) if (used[i] > 0) mstate = i;
// double score = 10.0F;
// if (40 <= mstate && mstate <= 60) {
// score += 20;
// } else if (26 <= mstate && mstate <= 39) {
// score += 25 + 1.5 * (40 - mstate);
// } else if (24 <= mstate && mstate <= 25) {
// score += 50 + 5 * (25 - mstate);
// } else if (mstate == 23) {
// score += 62;
// } else {
// score += 70 + 10 * (22 - mstate);
// }
// cout << "Max X: " << mstate << " Solution scores: " << score << " / 100\n";
return s;
}
