#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
vector<vector<int>> known_results;
bool ask(int a, int b)
{
//true if monster a wins
if (known_results[a][b]!=0)
{
if (known_results[a][b] == 1)
return 1;
return 0;
}
bool ans = Query(a, b);
if (ans)
{
known_results[a][b] = 1;
known_results[b][a] = -1;
}
else
{
known_results[a][b] = -1;
known_results[b][a] = 1;
}
return ans;
}
std::vector<int> Solve(int N) {
known_results = vector<vector<int>> (1005, vector<int> (1005, 0));
vector<int> temporary_results(1005, 0);
for (int i=1; i<N; i++)
{
vector<pii> curr;
for (int j=0; j<i; j++)
curr.push_back({temporary_results[j], j});
sort(curr.begin(), curr.end());
int range_lo = curr[0].first;
int range_hi = curr[i-1].first;
while ((range_hi - range_lo) > 11)
{
int range_mid = (range_lo + range_hi)/2;
int real_range_mid = -1;
int diff = N+5;
int ind = -1;
for (int j=0; j<i; j++)
if (abs(curr[j].first - range_mid) < diff)
{
real_range_mid = curr[j].first;
diff = abs(curr[j].first - range_mid);
ind = curr[j].second;
}
bool x = ask(i, ind);
if (x)
{
for (int j=0; j<i; j++)
if (((curr[j].first + 4) <= real_range_mid) and (known_results[i][curr[j].second] == 0))
{
known_results[i][curr[j].second] = 1;
known_results[curr[j].second][i] = -1;
}
range_lo = real_range_mid - 4;
}
else
{
for (int j=0; j<i; j++)
if (((curr[j].first - 4) >= real_range_mid) and (known_results[i][curr[j].second] == 0))
{
known_results[i][curr[j].second] = -1;
known_results[curr[j].second][i] = 1;
}
range_hi = real_range_mid + 4;
}
}
for (int j=0; j<i; j++)
{
if (ask(i, j))
temporary_results[i]++;
else
temporary_results[j]++;
}
}
vector<pii> curr;
for (int j=0; j<N; j++)
curr.push_back({temporary_results[j], j});
sort(curr.begin(), curr.end());
int lo_a = curr[0].second;
int lo_b = curr[1].second;
if (ask(lo_b, lo_a))
swap(lo_a, lo_b);
int hi_a = curr[N-2].second;
int hi_b = curr[N-1].second;
if (ask(hi_b, hi_a))
swap(hi_a, hi_b);
vector<int> answer = {lo_a, lo_b};
for (int j=2; j<(N-2); j++)
answer.push_back(curr[j].second);
answer.push_back(hi_a);
answer.push_back(hi_b);
vector<int> final_answer(N);
for (int j=0; j<N; j++)
final_answer[answer[j]] = j;
return final_answer;
}
