#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
#define trace(x) for (auto &el : x) cerr << el << " "
using pi = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pi>;
vi find_complete(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) {
int sc = 0; for (auto el : experiment) if (el == -1) sc++;
int sz = set<int>(experiment.begin(), experiment.end()).size();
if (sc > 0) sz = sz - 1 + sc;
return sz;
};
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;
}
/*
for the case of the graph being a path:
divide the graph into two disjoint sets ie. XYXYXY
for each colour, determine for each set X and Y how many elements in the entire graph have colour c
do this by setting all nodes of the other set to colour c then computing #(expected cmps) - #(actual cmps)
takes 2n = 500 queries
now for each colour that appears t > 0 times in a set, launch t binary searches of the form (first node where c appears >= i times?)
for i in range [1, t]
the sum of #(appearances in set) over all colours with t>0 is = size of set = n/2
in total doing this process for both sets will take 2 * (n/2) binary searches that use log₂(n/2) queries each, or for n = 250
it uses 2 * 125 * 7 = 1750 queries
in total 1750 + 500 = 2250
*/
vi find_path(int n, vi X, vi Y) {
vi G(n, 0);
auto expected_cmps = [&](vi e) {
int sz = 1; for (int i = 1; i < n; i++) if (!(e[i] == e[i-1] && e[i] != -1)) sz++;
return sz;
};
auto f = [&](int k, int colour, bool set1) {
vi e(n, n);
int LC = set1 ? -1 : colour, RC = set1 ? colour : -1;
for (int i = 0; i < k && (2*i) < n; i++) {
e[2*i] = LC;
if (2*i+1 < n) e[2*i+1] = RC;
}
return e;
};
auto g = [&](vi base, int colour, vi indices) {
for (auto el : indices) if (base[el] != n) base[el] = colour;
return base;
};
// set 1 is U.U.U.U., set2 is .V.V.V.V
int s1 = n/2, s2 = (n)/2;
for (int c = 0; c < n; c++) {
vi e1 = f(s1, c, true), e2 = f(s2, c, false);
int x1 = perform_experiment(e1), x2 = perform_experiment(e2);
if (x1 != expected_cmps(e1)) {
vi found;
while (expected_cmps(g(f(s1, c, true), c, found)) != x1) {
int lo = 0, hi = s1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
vi e = g(f(mid, c, true), c, found);
if (perform_experiment(e) == expected_cmps(e)) {
lo = mid + 1;
} else {
hi = mid;
}
}
found.push_back(2*(lo-1));
G[2*(lo-1)] = c;
}
}
if (x2 != expected_cmps(e2)) {
vi found;
while (expected_cmps(g(f(s2, c, false), c, found)) != x2) {
int lo = 0, hi = s2;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
vi e = g(f(mid, c, false), c, found);
if (perform_experiment(e) == expected_cmps(e)) {
lo = mid + 1;
} else {
hi = mid;
}
}
found.push_back(2*lo-1);
G[2*lo-1] = c;
}
}
}
return G;
}
vi find_colours(int n, vi X, vi Y) {
if (X.size() == (n * (n-1) / 2)) {
return find_complete(n, X, Y);
} else if (X.size() == n-1) {
return find_path(n, X, Y);
}
vi G(n, 0);
return G;
}
