#include "sphinx.h"
#include<bits/stdc++.h>
using namespace std;
// int x = perform_experiment(E);
vector<int> mur;
vector<int> rep;
int n;
int calc_compo(vector<pair<int,int>> v){
int nbc=v.size()*3-1;
if (v[0].first!=0 and v[0].second!=0){
nbc++;
}
if (v.back().first!=n-1 and v.back().second!=n-1){
nbc++;
}
return nbc;
}
void trouver(vector<pair<int,int>> candidats_voisins){
int couleur=0;
while (couleur<n-1 and !candidats_voisins.empty()){
//cout<<42<<endl;
/*for (auto i:candidats_voisins){
cout<<i.first<<" "<<i.second<<endl;
}*/
vector<int> quest=mur;
for (auto c:candidats_voisins){
quest[c.first]=-1; // la case de la question
quest[c.second]=couleur; // la case voisine pour la question
}
int nbcompo=calc_compo(candidats_voisins);
//cout<<nbcompo<<endl;
int vrai_nbcompo=perform_experiment(quest);
/*cout<<vrai_nbcompo<<endl;
for (int i:quest){
cout<<i<<" ";
}
cout<<endl;*/
if (vrai_nbcompo==nbcompo){
couleur++;
//cout<<42<<endl;
}
else {
//cout<<42<<endl;
int g=0,d=candidats_voisins.size()-1;
while (g<d){
int mil=(g+d+1)/2;
vector<int> nouv=mur;
vector<pair<int,int>> nouv_candidats={};
for (int i=g;i<mil;i++){
nouv[candidats_voisins[i].first]=-1;
nouv[candidats_voisins[i].second]=couleur;
nouv_candidats.push_back(candidats_voisins[i]);
}
int nbcompo=calc_compo(nouv_candidats);
int vrai_nbcompo=perform_experiment(nouv);
if (vrai_nbcompo==nbcompo){
g=mil;
}
else {
d=mil-1;
}
}
rep[candidats_voisins[g].first]=couleur;
vector<pair<int,int>> nouv_candidats={};
for (int i=0;i<(int)candidats_voisins.size();i++){
if (i!=g){
nouv_candidats.push_back(candidats_voisins[i]);
}
}
candidats_voisins=nouv_candidats;
}
}
for (auto c:candidats_voisins){
rep[c.first]=n-1;
}
}
vector<int> find_colours(int N,vector<int> deb,vector<int> fin) {
n=N;
for (int i=0;i<n;i++){
mur.push_back(n);
rep.push_back(n);
}
vector<pair<int,int>> quest={};
for (int i=0;i<n-1;i+=3){
quest.push_back({i,i+1});
}
trouver(quest);
//return {0};
//cout<<42<<endl;
//return {0};
quest={};
for (int i=1;i<n;i+=3){
quest.push_back({i,i-1});
}
trouver(quest);
quest={};
for (int i=2;i<n;i+=3){
quest.push_back({i,i-1});
}
trouver(quest);
quest={};
if (n%3==1){
trouver({{n-1,n-2}});
}
return rep;
}
