#include "prison.h"
#include <vector>
#include <map>
//#include <stdio.h>
namespace Solver {
std::vector<int> opt_split;
std::vector<int> nrstates; // nrstates[i] =def= numarul de stari necesare distingerii unui interval de lungime i
int ceil( int a, int b ) {
if( !a )
return 0;
return (a - 1) / b + 1;
}
void get_stats( int N ) {
nrstates.resize( N + 1, 0 );
opt_split.resize( N + 1, 0 );
opt_split[3] = 1;
nrstates[3] = 1;
for( int n = 4 ; n <= N ; n++ ){
if( 2 + nrstates[ceil( n - 2, 2 )] < 3 + nrstates[ceil( n - 2, 3 )] ){
nrstates[n] = 2 + nrstates[ceil( n - 2, 2 )];
opt_split[n] = 2;
}else{
nrstates[n] = 3 + nrstates[ceil( n - 2, 3 )];
opt_split[n] = 3;
}
}
}
// strategy
std::vector<int> split_len; // lungimea intervalului pe care trebuie sa il distingem
std::vector<int> splits; // numarul de bucket-uri pe care il folosim
std::vector<int> buk; // lungimea bucketului pe care il folosim
std::vector<std::vector<int>> poz_in_split; // pozitia in intervalul original pe care tb sa il distingem
std::vector<int> start_idx;
const int NIL = -1;
void strategy_stats( int N ) {
split_len.push_back( N );
poz_in_split.emplace_back( N + 1 );
for( int val = 1 ; val <= N ; val++ )
poz_in_split[0][val] = val - 1;
while( split_len.back() >= 3 ){
int L = split_len.back();
int S = opt_split[L];
splits.push_back( S );
int B = ceil( L - 2, S );
buk.push_back( B );
int idx = (int)poz_in_split.size() - 1;
poz_in_split.emplace_back( N + 1 );
for( int val = 1 ; val <= N ; val++ ){
int pis = poz_in_split[idx][val];
if( pis == NIL || pis == 0 || pis == L - 1 )
poz_in_split[idx+1][val] = NIL;
else
poz_in_split[idx+1][val] = (poz_in_split[idx][val] - 1) % B;
}
split_len.push_back( B );
}
// sume partiale
start_idx.push_back( 1 );
for( int S : splits )
start_idx.push_back( start_idx.back() + S );
}
int beats( int win, int lose ) {
if( lose == 0 )
return -1;
return -2;
}
std::vector<std::vector<int>> devise_strategy( int N ) {
get_stats( N );
strategy_stats( N );
std::vector<int> ret_idx;
std::vector<std::vector<int>> ret;
ret.emplace_back( N+1 );
bool t = 0;
ret[0][0] = t;
for( int val = 1 ; val <= N ; val++ ){
int P = poz_in_split[0][val];
if( P == 0 )
ret[0][val] = beats( !t, t );
else if( P == N - 1 )
ret[0][val] = beats( t, !t );
else if( (int)splits.size() )
ret[0][val] = start_idx[0] + (P - 1) / buk[0];
}
for( int idx = 0 ; idx < (int)splits.size() ; idx++ ){
t = !t;
// valori precalculate
int L = split_len[idx];
int B = buk[idx];
int S = splits[idx];
// state = start_idx[idx] + ((poz_in_split - 1) / B)
// asiguram ca am alocat memoria
int SI = start_idx[idx];
while( (int)ret.size() < SI + S ){
int buk_idx = (int)ret.size() - SI;
ret.emplace_back( N + 1 );
ret.back()[0] = t;
for( int val = 1 ; val <= N ; val++ ){
int P = poz_in_split[idx][val];
if( P == NIL )
ret.back()[val] = 0; // nu conteaza
else if( P == 0 )
ret.back()[val] = beats( !t, t );
else if( P == L - 1 )
ret.back()[val] = beats( t, !t );
else{
int t_buk_idx = (P - 1) / B;
if( t_buk_idx < buk_idx )
ret.back()[val] = beats( !t, t );
else if( t_buk_idx > buk_idx )
ret.back()[val] = beats( t, !t );
else{
int P2 = (P - 1) % B;
if( P2 == 0 )
ret.back()[val] = beats( !t, t );
else if( P2 == B - 1 )
ret.back()[val] = beats( t, !t );
else if( idx+1 < (int)splits.size() ) // evitam depasirea
ret.back()[val] = start_idx[idx+1] + (P2 - 1) / buk[idx+1];
}
}
}
}
}
return ret;
}
}
std::vector<std::vector<int>> devise_strategy( int N ) {
return Solver::devise_strategy( N );
}
