#include "prison.h"
#include <assert.h>
#include <vector>
#include <iostream>
using namespace std;
bool debug=0;
#define derr if(debug)cerr
#define pb push_back
vector<vector<int>> devise_strategy(int N) {
vector<vector<int>> answer;
vector<int> cur(N+1,0);
int ri;
cur[0]=0; // inspect box A!
for(int i=1; i<N+1; i++){
if(i <= 4096){
cur[i] = 1;
} else{
cur[i] = 2;
}
}
answer.pb(cur);
bool lastbox = 0;
int pmod = 8192;
int mod = 4096;
int nexti = 1;
while(pmod>4){
/*
basically zoom in:
1 m p 1 m
|---I---|--I--| => |---I---|--I--|
M P
*/
nexti += 2;
cur[0] = !lastbox;
// lastbox was in lower region
for(int i=1; i<N+1; i++){
ri = ((i-1)%pmod)+1;
if(ri <= mod){ // same zone
if(((ri-1)%mod)+1 <= mod/2){
cur[i] = nexti;
} else{
cur[i] = nexti+1;
}
} else{ // this box is greater.
cur[i] = ((lastbox+1)*-1);
}
}
answer.pb(cur);
// lastbox was in higher region
for(int i=1; i<N+1; i++){
ri = ((i-1)%pmod)+1;
if(ri <= mod){ // this box is lesser
cur[i] = ((!lastbox+1)*-1);
} else{ // same zone
if(((ri-1)%mod)+1 <= mod/2){
cur[i] = nexti;
} else{
cur[i] = nexti+1;
}
}
}
answer.pb(cur);
lastbox = !lastbox;
pmod/=2;
mod/=2;
}
// pmod=4, mod=2
// now we must explore box A.
cur[0] = 0;
// (24) valB is in the lower zone (1-2 MOD 4)
for(int i=1; i<N+1; i++){
ri = ((i-1)%pmod)+1;
if(ri>1) cur[i]=-2;
else cur[i]=-1;
}
answer.pb(cur);
// (25) valB in the upper zone (3-4 MOD 4)
for(int i=1; i<N+1; i++){
ri = ((i-1)%pmod)+1;
if(ri<4) cur[i]=-1;
else cur[i]=-2; // <-- !
}
answer.pb(cur);
derr<<"answer.size() >> "<<answer.size()<<"\n";
derr<<"previous box: "<<lastbox<<"\n";
derr<<"we know the answer %"<<pmod<<" is between 1 "<<mod<<"\n";
return answer;
}
