#include "sphinx.h"
#include <cassert>
#include <cstdio>
#include <queue>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int perform_experiment(std::vector<int> E);
vector<int>make(int n,int poz,int val)
{
std::vector<int> E(n);
for(int i=0; i<n; i++)
{
E[i]=val;
}
E[poz]=-1;
return E;
}
vector<int>coloreaza(int n,int off,int color,int st,int dr)
{
vector<int>vec(n);
for(int i=0;i<n;i++)
{
vec[i]=color;
}
for(int i=off;i<n;i+=2)
{
vec[i]=n;
}
for(int i=st;i<=dr;i++)
{
vec[(i-1)*2+off]=-1;
}
return vec;
}
vector<int>line(int n,int off,int color)
{
vector<int>gas;
int cate=(n+1-off)/2;
int st=1,dr=cate;
while(perform_experiment(coloreaza(n,off,color,st,dr))!=n)
{
while(st<dr)
{
int mij=(st+dr)/2;
if(perform_experiment(coloreaza(n,off,color,st,mij))!=n)
{
dr=mij;
}
else
{
st=mij+1;
}
}
gas.push_back((dr-1)*2+off);
st=dr+1;
dr=cate;
}
return gas;
}
vector<int>cul;
void solve(int n,int off)
{
for(int color=0;color<n;color++)
{
vector<int>gas=line(n,off,color);
for(auto x:gas)
{
cul[x]=color;
}
}
}
int check(int n,int poz,int prefix)
{
vector<int>vec(n);
int nxt=0,done=0;
for(int i=0;i<n;i++)
{
if(i==poz)
{
vec[i]=-1;
}
else
{
if(nxt>prefix)
{
vec[i]=n;
done=1;
}
else
{
vec[i]=nxt;
nxt++;
}
}
}
if(perform_experiment(vec)==prefix+1+done)
{
return 1;
}
return 0;
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y)
{
std::vector<int> E(N, -1);
vector<int>rasp(N);
int n=N;
if(n<=50)
{
int n=N;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
int rez=perform_experiment(make(N,i,j));
if(rez==1)
{
rasp[i]=j;
}
}
}
return rasp;
}
else if(X.size()==n-1)
{
cul.resize(n);
for(int off=0;off<=1;off++)
{
solve(n,off);
}
}
else
{
cul.resize(n);
for(int i=0;i<n;i++)
{
int st=0,dr=n-1;
while(st<dr)
{
int mij=(st+dr)/2;
if(check(n,i,mij)==1)
{
dr=mij;
}
else
{
st=mij+1;
}
}
cul[i]=dr;
}
}
return cul;
}
