#include "prison.h"
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> res;
int N;
int max_used_idx = 0;
bool used[100];
struct Range{
int l, r;
Range(){}
Range(int left, int right){
l = left;
r = right;
}
};
vector<vector<int>> devise_strategy(int _N) {
N = _N;
res.resize(100);
for(int i = 0; i < 100; i++)
res[i].resize(N+1);
vector<Range> left_ranges;
vector<Range> right_ranges;
used[0] = true;
right_ranges.push_back(Range(1, N));
for(int idx = 0; idx < 100; idx++){
if(!used[idx])
continue;
// turn is equal to depth % 2
// depth is equal to idx + 1 / 2
int depth = (idx+1)/2;
int turn = depth % 2;
if(idx % 2 == 1){
// new depth, so first reset!
vector<Range> left_ranges_new;
vector<Range> right_ranges_new;
for(Range rng : left_ranges){
int l = rng.l;
int r = rng.r;
l++;
r--;
int mid = (l + r) / 2;
left_ranges_new.push_back(Range(l, mid));
if(mid + 1 <= r)
right_ranges_new.push_back(Range(mid+1, r));
}
for(Range rng : right_ranges){
int l = rng.l;
int r = rng.r;
l++;
r--;
int mid = (l + r) / 2;
left_ranges_new.push_back(Range(l, mid));
if(mid + 1 <= r)
right_ranges_new.push_back(Range(mid+1, r));
}
left_ranges = left_ranges_new;
right_ranges = right_ranges_new;
/* cout << "Depth " << depth << " left:" << endl;
for(Range rng : left_ranges)
cout << rng.l << " - " << rng.r << endl; */
res[idx][0] = turn;
// now process
for(int i = 1; i <= N; i++){
bool in_range = false;
Range rng;
bool borders_small = false;
bool borders_big = false;
for(Range r : left_ranges){
if(i >= r.l && i <= r.r){
in_range = true;
rng = r;
break;
}else if(i == r.l - 1){
borders_small = true;
}else if(i == r.r + 1){
borders_big = true;
}
}
if(!in_range){
// not in the right range, so I'm in a right range... ie. bigger
if(borders_small){
if(turn == 0)
res[idx][i] = -1; // im smaller
else
res[idx][i] = -2;
}else if(borders_big){
if(turn == 0)
res[idx][i] = -2; // im bigger
else
res[idx][i] = -1;
}else if(turn == 0)
res[idx][i] = -2; // im bigger
else
res[idx][i] = -1;
}else if(i == rng.l){
// im definitely smaller
if(turn == 0)
res[idx][i] = -1; // im smaller
else
res[idx][i] = -2;
}else if(i == rng.r){
// im definitely bigger
if(turn == 0)
res[idx][i] = -2; // im bigger
else
res[idx][i] = -1;
}else{
int mid = (rng.l + rng.r) / 2;
if(i <= mid){
// left je sljedeci + 1 jer sam u lijevom
res[idx][i] = idx+2;
used[idx+2] = true;
}else{
// right je sljedeci + 2 jer sam u lijevom
res[idx][i] = idx+3;
used[idx+3] = true;
}
}
}
}else{
/* cout << "Depth " << depth << " right:" << endl;
for(Range rng : right_ranges)
cout << rng.l << " - " << rng.r << endl; */
res[idx][0] = turn;
// same depth, but right
for(int i = 1; i <= N; i++){
bool in_range = false;
Range rng;
bool borders_small = false;
bool borders_big = false;
for(Range r : right_ranges){
if(i >= r.l && i <= r.r){
in_range = true;
rng = r;
break;
}else if(i == r.l - 1){
borders_small = true;
}else if(i == r.r + 1){
borders_big = true;
}
}
if(!in_range){
// not in the right range, so I'm in a left range... ie. smaller
if(borders_small){
if(turn == 0)
res[idx][i] = -1; // im smaller
else
res[idx][i] = -2;
}else if(borders_big){
if(turn == 0)
res[idx][i] = -2; // im bigger
else
res[idx][i] = -1;
}else if(turn == 0)
res[idx][i] = -1; // im smaller
else
res[idx][i] = -2;
}else if(i == rng.l){
// im definitely smaller
if(turn == 0)
res[idx][i] = -1; // im smaller
else
res[idx][i] = -2;
}else if(i == rng.r){
// im definitely bigger
if(turn == 0)
res[idx][i] = -2; // im bigger
else
res[idx][i] = -1;
}else{
int mid = (rng.l + rng.r) / 2;
if(i <= mid){
// left je sljedeci jer sam u desnom
res[idx][i] = idx+1;
used[idx+1] = true;
}else{
// right je sljedeci + 1 jer sam u desnom
res[idx][i] = idx+2;
used[idx+2] = true;
}
}
}
}
}
int max_used = 0;
for(int i = 0; i < 100; i++)
if(used[i])
max_used = max(max_used, i);
res.resize(max_used + 1);
//for(int i = 0; i < max_used; i++)
// cout << res[i][2] << " " << res[i][4] << " turn is " << res[i][0] << endl;
return res;
}
