#include<bits/stdc++.h>
#include "monster.h"
using namespace std;
const int MAX_VAL=1000+5;
int nbVal,nbReq;
int memo[MAX_VAL][MAX_VAL];
int quest(int a,int b) {
if (a>b) {
return 1-quest(b,a);
}
if (memo[a][b]!=-1) {
return memo[a][b];
}
if (Query(a,b)) {
memo[a][b]=1;
}
else {
memo[a][b]=0;
}
nbReq++;
return memo[a][b];
}
vector<int> calc(vector<int> pers) {
int taille=pers.size();
if (taille==1) {
return pers;
}
int mid=taille/2;
vector<int> gau,dro,ans;
for (int i=0;i<mid;i++) {
gau.push_back(pers[i]);
}
for (int i=mid;i<taille;i++) {
dro.push_back(pers[i]);
}
gau=calc(gau);
dro=calc(dro);
while (!gau.empty() or !dro.empty()) {
if (gau.empty()) {
ans.push_back(dro.back());
dro.pop_back();
}
else if (dro.empty()) {
ans.push_back(gau.back());
gau.pop_back();
}
else {
if (quest(gau.back(),dro.back())==1) {
ans.push_back(gau.back());
gau.pop_back();
}
else {
ans.push_back(dro.back());
dro.pop_back();
}
}
}
reverse(ans.begin(),ans.end());
/*for (int i:ans) {
cout<<i<<" ";
}
cout<<endl;*/
return ans;
}
vector<int> Solve(int N) {
nbVal=N;
for (int i=0;i<nbVal;i++) {
for (int j=0;j<nbVal;j++) {
memo[i][j]=-1;
}
}
vector<int> rep,init,ans;
for (int i=0;i<nbVal;i++) {
init.push_back(i);
}
srand(time(NULL));
random_shuffle(init.begin(),init.end());
rep=calc(init);
/*for (int i:rep) {
cout<<i<<" ";
}
cout<<endl;*/
int pos=0,deb,fin;
while (pos<nbVal) {
deb=pos;
if (deb==0) {
vector<int> listeInf;
for (int i=1;i<nbVal;i++) {
if (quest(rep[0],rep[i])==1) {
listeInf.push_back(i);
//cout<<i<<" ";
}
}
//cout<<endl;
if (listeInf.size()==1) {
fin=listeInf.back();
vector<int> liste2;
for (int i=0;i<nbVal;i++) {
if (i!=fin and quest(rep[fin],rep[i])==1) {
liste2.push_back(i);
}
}
if (liste2.size()==1) {
fin=0;
}
else {
fin=1;
}
}
else {
listeInf.pop_back();
fin=listeInf.back();
}
pos=fin;
while (deb<fin) {
swap(rep[deb],rep[fin]);
deb++;
fin--;
}
}
else {
while (quest(rep[deb-1],rep[pos])==0) {
pos++;
}
fin=pos;
//cout<<deb<<" "<<fin<<endl;
while (deb<fin) {
swap(rep[deb],rep[fin]);
deb++;
fin--;
}
}
pos++;
}
/*for (int i:rep) {
cout<<i<<" ";
}
cout<<endl;*/
ans.resize(nbVal);
for (int i=0;i<nbVal;i++) {
ans[rep[i]]=i;
}
/*for (int i:ans) {
cout<<i<<" ";
}
cout<<endl;
cout<<"Nombre de questions : "<<nbReq<<endl;*/
return ans;
}
