#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
vi find_colours(int n, vi X, vi Y) {
vi G(n, 0);
auto first_k_colours = [&](int target, int k) {
if (k >= n) {
vi e(n, n-1); e[target] = 1;
return e;
}
vi e(n, n); e[target] = -1;
int colour = 0;
for (int i = 0; i < target && k > 0; i++) {
e[i] = colour;
k--; colour++;
}
for (int i = target + 1; i < n && k > 0; i++) {
e[i] = colour;
k--; colour++;
}
return e;
};
auto expected_cmps = [](vi experiment) {
return set<int>(experiment.begin(), experiment.end()).size();
};
for (int i = 0; i < n; i++) {
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
vi e = first_k_colours(i, mid);
int x = perform_experiment(e);
if (x == expected_cmps(e)) {
lo = mid + 1;
} else {
hi = mid;
}
}
G[i] = lo - 1;
}
return G;
}
