#include "sphinx.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 255;
int n, m;
int a[maxn];
vector < int > even, odd;
int ask_even(int st, int fi, int c)
{
//cout << "ask " << endl;
vector < int > g(n, 0);
for (int i = 0; i < n; ++ i)
{
if(i & 1)g[i] = c;
else if(i < st || i > fi)g[i] = n;
else g[i] = -1;
}
int fb = perform_experiment(g);
return fb;
}
int ask_odd(int st, int fi, int c)
{
//cout << "ask 2 " << endl;
vector < int > g(n, 0);
for (int i = 0; i < n; ++ i)
{
if(i % 2 == 0)g[i] = c;
else if(i < st || i > fi)g[i] = n;
else g[i] = -1;
}
int fb = perform_experiment(g);
return fb;
}
std::vector<int> find_colours(int N, std::vector<int> X, std::vector<int> Y)
{
n = N;
m = X.size();
memset(a, -1, sizeof(a));
for (int i = 0; i < n; ++ i)
{
if(i % 2 == 0)even.pb(i);
else odd.pb(i);
}
for (int c = 0; c < n; ++ c)
{
if(even.size() == 0)break;
int pre = -1;
if(ask_even(-1, n, c) == n)
{
continue;
}
// cout << pre << " " << even.size() << endl;
int sz = even.size();
while(pre < sz)
{
// cout << "ehere " << endl;
int l = pre+1, r = sz-1, mid, ans = sz; /// pyrvoto koeto naebava
while(l <= r)
{
mid = (l + r)/2;
if(ask_even(even[pre+1], even[mid], c) == n)
{
l = mid + 1;
}
else
{
r = mid - 1;
ans = mid;
}
}
pre = ans;
if(ans < even.size())
{
int pos = even[ans];
a[pos] = c;
}
}
even.clear();
for (int j = 0; j < n; ++ j)
{
if(j % 2 == 0)
{
if(a[j] == -1)even.pb(j);
}
}
}
for (int c = 0; c < n; ++ c)
{
if(odd.size() == 0)break;
int v = ask_odd(-1, n, c);
int cnt = (n - v)/2 + (n - v)%2;
if(v == n)
{
continue;
}
int pre = -1;
int sz = odd.size();
while(cnt --)
{
int l = pre+1, r = sz-1, mid, ans = sz; /// pyrvoto koeto naebava
while(l <= r)
{
mid = (l + r)/2;
if(ask_odd(odd[pre+1], odd[mid], c) == n)
{
l = mid + 1;
}
else
{
r = mid - 1;
ans = mid;
}
}
pre = ans;
if(ans < odd.size())
{
int pos = odd[ans];
a[pos] = c;
}
}
odd.clear();
for (int j = 0; j < n; ++ j)
{
if(j & 1)
{
if(a[j] == -1)odd.pb(j);
}
}
}
vector < int > res;
for (int i = 0 ;i < n; ++ i)
res.pb(a[i]);
return res;
}
