#include "prison.h"
#include <vector>
//#include <iostream>
typedef std::pair<int, int> ii;
typedef std::vector<int> vi;
typedef std::vector<ii> vii;
typedef std::vector<vi> vvi;
typedef std::vector<vii> vvii;
vvi res(0, vi(0));
int maximal_number = 21;
int N = 5000;
vvii ranges(int n) {
vvii res(0);
res.push_back(vii{ ii(1, n) });
for (int i = 0; i < 10; i++) {
vii new_ranges(0);
for (int j = 0; j < int(res[i].size()); j++) {
int small = res[i][j].first;
int large = res[i][j].second;
small += 1;
large -= 1;
int mid = (small + large) / 2;
new_ranges.push_back(ii(small, mid));
new_ranges.push_back(ii(mid + 1, large));
}
res.push_back(new_ranges);
}
return res;
}
void init_res(int N) {
res.resize(maximal_number + 1, vi(N + 1));
for (int i = 0; i <= maximal_number; i++) {
for (int j = 0; j <= N; j++) {
res[i][j] = 0;
}
}
}
void set_res_bag_choice(int N) {
for (int i = 0; i <= maximal_number; i++) {
res[i][0] = 0;
}
for (int i = 0; i <= maximal_number; i++) {
if (1 + i + i <= maximal_number) {
res[1 + i + i][0] = 1;
}
if (2 + i + i <= maximal_number) {
res[2 + i + i][0] = 1;
}
}
}
void set_0_number() {
for (int i = 1; i <= 5000; i++) {
int val = 0;
if (i == 1) {
val = -1;
}
else if (i == 5000) {
val = -2;
}
else if (i <= 2500) {
val = 1;
}
else {
val = 2;
}
res[0][i] = val;
}
}
void set_number(int number, vii possible_number_ranges) {
bool last_is_smaller = (number % 2) == 1;
bool last_was_a = ((number % 4) == 1) || ((number % 4 == 2));
int im_smaller_indicator = -1;
int im_bigger_indicator = -2;
if (last_was_a) {
im_smaller_indicator = -2;
im_bigger_indicator = -1;
}
int next_value_small = 1 + number + (number % 2);
int next_value_large = next_value_small + 1;
for (int i = 0; i < int(possible_number_ranges.size()); i += 2) {
ii smaller = possible_number_ranges[i];
ii larger = possible_number_ranges[i + 1];
res[number][smaller.first - 1] = im_smaller_indicator;
res[number][smaller.first] = im_smaller_indicator;
if (last_is_smaller) {
res[number][smaller.second] = im_bigger_indicator;
}
else {
res[number][smaller.second] = im_smaller_indicator;
}
res[number][larger.second + 1] = im_bigger_indicator;
res[number][larger.second] = im_bigger_indicator;
if (last_is_smaller) {
res[number][larger.first] = im_bigger_indicator;
}
else {
res[number][larger.first] = im_smaller_indicator;
}
for (int j = smaller.first + 1; j < smaller.second; j++) {
res[number][j] = next_value_small;
if (!last_is_smaller) {
res[number][j] = im_smaller_indicator;
}
}
for (int j = larger.first + 1; j < larger.second; j++) {
res[number][j] = next_value_large;
if (last_is_smaller) {
res[number][j] = im_bigger_indicator;
}
}
}
}
void set_last_number(int number, vii last_possible_number_ranges) {
bool last_was_a = ((number % 4) == 1) || ((number % 4 == 2));
int im_smaller_indicator = -1;
int im_bigger_indicator = -2;
if (last_was_a) {
im_smaller_indicator = -2;
im_bigger_indicator = -1;
}
for (int i = 0; i < int(last_possible_number_ranges.size()); i+= 2) {
ii smaller = last_possible_number_ranges[i];
ii larger = last_possible_number_ranges[i + 1];
int first_diff = smaller.second - smaller.first;
int second_diff = larger.second - larger.first;
if (first_diff == 2 && second_diff == 2) {
res[number][smaller.first] = im_smaller_indicator;
res[number][smaller.second] = im_bigger_indicator;
res[number][larger.first] = im_smaller_indicator;
res[number][larger.second] = im_bigger_indicator;
}
else if (first_diff == 2 && second_diff == 1) {
res[number][smaller.first] = im_smaller_indicator;
res[number][smaller.second] = im_bigger_indicator;
}
}
}
vvi devise_strategy(int n) {
vvii ranges_vec = ranges(N);
init_res(N);
set_res_bag_choice(N);
set_0_number();
int counter = 1;
for (int i = 1; true; i++) {
if ((i % 2 == 1) && i != 1) {
counter += 1;
}
if (counter >= int(ranges_vec.size())) {
break;
}
set_number(i, ranges_vec[counter]);
}
set_last_number(maximal_number, ranges_vec[int(ranges_vec.size()) - 1]);
vvi result(maximal_number + 1, vi(n + 1));
for (int i = 0; i <= maximal_number; i++) {
result[i][0] = res[i][0];
for (int j = 1; j <= n; j++) {
result[i][j] = res[i][j];
if (res[i][j] > maximal_number) {
result[i][j] = maximal_number;
}
if (res[i][j] == 0) {
result[i][j] = maximal_number;
}
}
}
return result;
}
/*int main() {
vvi v = devise_strategy(5000);
vvii vec = ranges(5000);
vi diffs(10);
return 0;
}*/
//number ->
// looking at first_bag -> (0,3,4,7,8,11,12,15,16,19,20
// looking at second_bag -> (1,2,5,6,9,10,13,14,17,18
