#include "sphinx.h"
#include <bits/stdc++.h>
using namespace std;
// Cache to prevent duplicate experiments for the exact same parameters
map<pair<vector<int>, int>, int> memo;
int count_matching(int n, const vector<int>& nodes_to_test, int target_color) {
if (nodes_to_test.empty()) return 0;
// Sort to ensure cache consistency
vector<int> sorted_nodes = nodes_to_test;
sort(sorted_nodes.begin(), sorted_nodes.end());
if (memo.count({sorted_nodes, target_color})) return memo[{sorted_nodes, target_color}];
vector<int> E(n, target_color);
for (int idx : nodes_to_test) E[idx] = -1;
int res = perform_experiment(E);
// Path logic: each non-matching node in an independent set adds 2 components
int non_matching = (res - 1) / 2;
int matching = (int)nodes_to_test.size() - non_matching;
return memo[{sorted_nodes, target_color}] = matching;
}
// Recursive function to find all occurrences of a color in a subset of nodes
void find_all_occurrences(int n, const vector<int>& candidates, int target_color, vector<int>& final_colors) {
int total = count_matching(n, candidates, target_color);
if (total == 0) return;
// If all nodes in this range match the color
if (total == (int)candidates.size()) {
for (int idx : candidates) final_colors[idx] = target_color;
return;
}
// Otherwise, split and recurse
int mid = candidates.size() / 2;
vector<int> left_side(candidates.begin(), candidates.begin() + mid);
vector<int> right_side(candidates.begin() + mid, candidates.end());
find_all_occurrences(n, left_side, target_color, final_colors);
find_all_occurrences(n, right_side, target_color, final_colors);
}
vector<int> find_colours(int n, vector<int> x, vector<int> y) {
vector<int> final_colors(n, -1);
vector<int> sets[2];
for (int i = 0; i < n; i++) sets[i % 2].push_back(i);
// We only need to check N-1 colors
for (int c = 0; c < n - 1; c++) {
for (int s = 0; s < 2; s++) {
// Only search among nodes that don't have a color yet
vector<int> unknown_in_set;
for (int idx : sets[s]) {
if (final_colors[idx] == -1) unknown_in_set.push_back(idx);
}
if (!unknown_in_set.empty()) {
find_all_occurrences(n, unknown_in_set, c, final_colors);
}
}
}
// Assign the final color (N-1) to anyone still missing
for (int i = 0; i < n; i++) {
if (final_colors[i] == -1) final_colors[i] = n - 1;
}
return final_colors;
}
