#include "prison.h"
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> res;
int N;
int max_used_idx = 0;
bool used[100];
void set_strategy(int turn, int idx, vector<pair<int, int>> ranges, bool is_left){
res[idx][0] = turn;
used[idx] = true;
max_used_idx = max(idx, max_used_idx);
bool needs_left = false;
bool needs_right = false;
vector<pair<int, int>> left_ranges;
vector<pair<int, int>> right_ranges;
for(pair<int, int> range : ranges){
int l = range.first;
int r = range.second;
//l++;
//r--;
if(r - l >= 1){
int mid = (l+r) / 2;
left_ranges.push_back({l, mid});
needs_left = true;
if(mid+1 <= r){
right_ranges.push_back({mid+1, r});
needs_right = true;
}
}
}
//cout << "still alive" << endl;
int left_idx = -5;
int right_idx = -5;
if(needs_left){
for(int i = 0; i < 100; i++){
if(used[i] == false){
left_idx = i;
used[i] = true;
break;
}
}
}
if(needs_right){
for(int i = 0; i < 100; i++){
if(used[i] == false){
right_idx = i;
used[i] = true;
break;
}
}
}
for(int i = 1; i <= N; i++){
bool in_range = false;
pair<int, int> range;
for(pair<int, int> range_t : ranges){
if(i >= range_t.first && i <= range_t.second){
in_range = true;
range = range_t;
}
}
if(!in_range){
// znamo sta smo
if(is_left){
// ovo je indeks za lijevi range, znaci ja sam desni -> veci!
// dakle rjesenje je druga vreca jer je ona manja
if(turn == 0)
res[idx][i] = -2;
else
res[idx][i] = -1;
}else{
// ovo je indeks za desni range, znaci ja sam lijevo -> manji!
// dakle rjesenje je ova vreca (ja)
if(turn == 0)
res[idx][i] = -1;
else
res[idx][i] = -2;
}
}else{
// provjerimo jesmo li na cosku range-a
// ili na nekoj strani
if(i == range.first){
// mi smo sigurno manji
if(turn == 0)
res[idx][i] = -1;
else
res[idx][i] = -2;
}else if(i == range.second){
// mi smo sigurno veci
if(turn == 0)
res[idx][i] = -2;
else
res[idx][i] = -1;
}else{
//range.first++;
//range.second--;
int mid = (range.first + range.second)/2;
// idemo ili lijevo (idx+1) ili desno (idx+2)
if(i <= mid)
res[idx][i] = left_idx;
else
res[idx][i] = right_idx;
}
}
}
//cout << left_idx << " " << right_idx << endl;
if(needs_left){
if(turn == 0)
set_strategy(1, left_idx, left_ranges, true);
else
set_strategy(0, left_idx, left_ranges, true);
}
if(needs_right){
if(turn == 0)
set_strategy(1, right_idx, right_ranges, false);
else
set_strategy(0, right_idx, right_ranges, false);
}
}
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<pair<int, int>> ranges;
ranges.push_back({1, N});
set_strategy(0, 0, ranges, true);
res.resize(max_used_idx+1);
return res;
}
