#include "monster.h"
#include <random>
#include <iostream>
#include <algorithm>
#define vi vector<int>
#define uid uniform_int_distribution<int>
using namespace std;
/*
Observations:
- P_i will win against min(1, max(P_i, N - 2)) opponents.
- Sorting with the comparator will give us an array such that it can be divided into
consecutive groups of [x, x - 1, ....], [y, y - 1, y - 2....], ...
- There are no two consecutive groups of size 1
- Each consecutive group's size is at most log N + 1.
*/
int done[1001][1001];
inline bool ask(int a, int b)
{
bool ret = 0;
if (a > b) {swap(a, b); ret = 1;}
if (done[a][b] == -1) done[a][b] = Query(a, b);
return ret ^ done[a][b];
}
int n, P[1001], A[1001];
inline void mergeSort(int L, int R)
{
if (L < R)
{
int M = L + R >> 1;
mergeSort(L, M);
mergeSort(M + 1, R);
for (int i = L; i <= R; i++) A[i] = P[i];
int l = L, r = M + 1;
for (int i = L; i <= R; i++)
{
if (l <= M && r <= R)
{
if (ask(A[r], A[l])) P[i] = A[l++];
else P[i] = A[r++];
}
else if (l <= M) P[i] = A[l++];
else P[i] = A[r++];
}
}
}
vector<int> Solve(int N)
{
vi ret(N); n = N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++) done[i][j] = -1;
P[i] = i;
}
mergeSort(0, N - 1);
int cnt = 0, prev = 1;
for (int i = 2; i < 22 && i <= prev + 11 && i < N; i++)
{
if (ask(P[0], P[i])) {cnt++; prev = i;}
}
int cur;
if (cnt > 1) {reverse(P, P + cnt + 1); cur = cnt;}
else if (cnt == 1 && prev > 2)
{
if (ask(P[1], P[prev])) {cur = 0;}
else {reverse(P, P + 2); cur = 1;}
}
else
{
int tp = 1;
for (int i = 3; i < 14 && i < N; i++)
{
if (ask(P[1], P[i])) {tp = 0; break;}
}
reverse(P, P + tp + 1); cur = tp;
}
for (int i = cur + 1; i < N; i++)
{
if (ask(P[cur], P[i]))
{
reverse(P + cur + 1, P + i + 1);
cur = i;
}
}
for (int i = 0; i < N; i++) ret[P[i]] = i;
return ret;
}
