#include "sphinx.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
ordered_set os;
int leftCOLOR=0;
int rightCOLOR=0;
int kcol=0;
int n;
vector<int> E;
vector<int> G;
queue<int> torem;
int eval(int l, int r, int val){
return (r-l+1)-(val-1)/2;
}
void dc(int l, int r, int val){
if(val==0) return;
if(l==r){
int x=*os.find_by_order(l);
G[x]=kcol;
torem.push(x);
return;
}
int mid=(l+r)/2;
for (int i = 0; i < n; i++){
if(os.find(i)!=os.end()&&(int)os.order_of_key(i)>=l&&(int)os.order_of_key(i)<=mid) E[i]=-1;
else E[i]=kcol;
}
int exp=eval(l,mid,perform_experiment(E));
dc(l,mid,exp);
dc(mid+1,r,val-exp);
}
vector<int> find_colours(int N, vector<int> X, vector<int> Y) {
n=N;
//determine left color
E.resize(N,N);
G.resize(N,N);
E[0]=-1;
E[1]=leftCOLOR;
int pf=perform_experiment(E);
while((pf==3&&N>2)||(pf==2&&N==2)){
leftCOLOR++;
E[1]=leftCOLOR;
pf=perform_experiment(E);
}
G[0]=leftCOLOR;
//determine right color
for (int i = 0; i < n; i++) E[i]=N;
E[N-1]=-1;
E[N-2]=rightCOLOR;
pf=perform_experiment(E);
while((pf==3&&N>2)||(pf==2&&N==2)){
rightCOLOR++;
E[N-2]=rightCOLOR;
pf=perform_experiment(E);
}
G[N-1]=rightCOLOR;
for (int i = 1; i < n-1; i++)
{
if(i%2==0) os.insert(i);
}
// les truc pair
while(kcol<n)
{
for (int i = 0; i < n; i++)
{
if(os.find(i)!=os.end()) E[i]=-1;
else E[i]=kcol;
}
int val=perform_experiment(E);
if(os.empty()) break;
dc(0,sz(os)-1,eval(0,sz(os)-1,val));
while(!torem.empty()){
int u=torem.front(); torem.pop();
os.erase(os.find_by_order(os.order_of_key(u)));
}
kcol++;
}
kcol=0;
for (int i = 1; i < n-1; i++)
{
if(i%2) os.insert(i);
}
while(kcol<n)
{
for (int i = 0; i < n; i++)
{
if(os.find(i)!=os.end()) E[i]=-1;
else E[i]=kcol;
}
int val=perform_experiment(E);
if(os.empty()) break;
dc(0,sz(os)-1,eval(0,sz(os)-1,val));
while(!torem.empty()){
int u=torem.front(); torem.pop();
os.erase(os.find_by_order(os.order_of_key(u)));
}
kcol++;
}
kcol=0;
return G;
}
