#include <bits/stdc++.h>
#include "sphinx.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
const int nax = 5e5+5;
int n;
vector<int> ans;
vector<int> mark(int l,int r,int c,int idx){
vector<int> cur(n,c);
int mid=(r+l)/2;
for (int i = l; i <= mid; ++i)
{
cur[i]=(idx ? c : -1);
}
for (int i = mid+1; i <= r; ++i)
{
cur[i]=(idx ? -1 : c);
}
return cur;
}
void daq(int l,int r,vector<int> colors){
int mid=(r+l)/2;
if(r-l+1==2){
if(colors.size()==1){
daq(l,l,colors);
daq(r,r,colors);
}else{
int a=colors[0];
int b=colors.back();
if(perform_experiment(mark(l,mid,a,0)) == 1){
daq(r,r,{b});
daq(l,l,{a});
}else{
daq(l,l,{b});
daq(r,r,{a});
}
}
return;
}else if(r==l){
ans[l]=colors.back();
return;
}
vector<int> left;
vector<int> right;
for(auto u : colors){
int fir = perform_experiment(mark(l,r,N,0));
if(perform_experiment(mark(l,r,u,0))<fir) left.push_back(u);
else if(r-l+1<n) right.push_back(u);
}
if(r-l+1==n){
int fir = perform_experiment(mark(l,r,N,1));
for(auto u : colors){
if(perform_experiment(mark(l,r,u,1))<fir){
right.push_back(u);
}
}
}else{
int fir = perform_experiment(mark(l,r,N,1));
for(auto u:left){
if(perform_experiment(mark(l,r,u,1))<fir) right.push_back(u);
}
}
daq(l,mid,left);
daq(mid+1,r,right);
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y) {
n=N;
vector<int> colors(N);
ans.resize(N);
for (int i = 0; i < N; ++i) colors[i]=i;
if(n<=50){
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
vector<int> tab(N,i);
tab[j]=-1;
if(perform_experiment(tab)==1) ans[j]=i;
}
}
}else daq(0,N-1,colors);
return ans;
}
