#include "monster.h"
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void print(string pre, vector<int> a) {
return;
cout << pre << " ";
for (int i = 0; i < a.size(); ++i) {
cout << a[i] << " ";
}
cout << "\n";
}
int higher[1024];
map<pair<int, int>, int> quer;
bool cmp(int a, int b, int N) {
if (a >= N) return true;
if (b >= N) return false;
//cout << a << " " << b << "\n";
bool q = Query(a, b);
if (q) higher[a]++; else higher[b]++;
return q;
}
bool compare(int a, int b, int N) {
if (quer[{a, b}] != 0) return quer[{a, b}] == 2;
bool q = cmp(a, b, N);
quer[{a, b}] = q ? 2 : 1;
quer[{b, a}] = q ? 1 : 2;
return q;
}
vector<int> sort(int l, int o, int N) {
if (l == 0) return std::vector<int>{o};
vector<int> a = sort(l - 1, o, N);
vector<int> b = sort(l - 1, o + (1 << (l - 1)), N);
vector<int> c(a.size() + b.size());
int iA = 0;
int iB = 0;
for (int i = 0; i < c.size(); ++i) {
if (iA < a.size() && iB < b.size()) {
if (compare(a[iA], b[iB], N)) {
c[i] = b[iB++];
} else {
c[i] = a[iA++];
}
} else {
if (iA == a.size()) {
c[i] = b[iB++];
} else {
c[i] = a[iA++];
}
}
}
return c;
}
void rev(vector<int> &T, int a, int b) {
for (int i = 0; i < (1 + b - a) / 2; ++i) {
swap(T[a + i], T[b - i]);
}
}
int findMin(int N) {
vector<int> low;
for (int i = 0; i < N; ++i) {
if (higher[i] <= 3) low.push_back(i);
}
print("possible: ", low);
int ii;
for (int i = 0; i < low.size(); ++i) {
ii = i + 1;
while (ii < low.size() && higher[i] <= 3) {
compare(low[i], low[ii], N);
ii++;
}
}
vector<int> possible;
for (int i = 0; i < low.size(); ++i) {
if (higher[low[i]] <= 3) possible.push_back(low[i]);
}
print("possible: ", possible);
for (int i = 0; i < possible.size(); ++i) {
for (int j = i + 1; j < possible.size(); ++j) {
compare(possible[i], possible[j], N);
}
}
vector<int> min;
for (int i = 0; i < possible.size(); ++i) {
if (higher[possible[i]] == 1) min.push_back(possible[i]);
}
print("last: ", min);
//for (int i = 0; i < N; ++i) cout << higher[i]; cout << "\n";
return compare(min[0], min[1], N) ? min[0] : min[1];
}
std::vector<int> Solve(int N) {
vector<int> T = sort(10, 0, N);
int ind;
int x = findMin(N);
for (int i = 0; i < N; ++i) {
if (T[i] == x) ind = i;
}
rev(T, 0, ind);
for (int s = ind; s < N - 1;) {
for (int i = s + 1; i < N; ++i) {
if (compare(T[s], T[i], N)) {
rev(T, s + 1, i);
s = i;
break;
}
if (i == N - 1) return {0};
}
}
vector<int> erg = vector<int>(N, 0);
for (int i = 0; i < N; ++i) {
erg[T[i]] = i;
}
return erg;
}
