#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;
}
int sz = even.size();
while(pre < sz){
int l = pre+1, r = sz-1, mid, ans = sz;
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;
}
