#include "monster.h"
namespace {
bool example_variable;
}
void merge_sort(std::vector<int>& v, int l, int r) {
if (r - l <= 1) return;
int mid = (l + r) / 2;
merge_sort(v, l, mid);
merge_sort(v, mid, r);
std::vector<int> result;
result.reserve(r - l);
int i = l, j = mid;
while (i < mid && j < r) {
bool fight = Query(v[i], v[j]);
if (fight) {
result.push_back(v[j]);
j++;
} else {
result.push_back(v[i]);
i++;
}
}
while (i < mid) {
result.push_back(v[i]);
i++;
}
while (j < r) {
result.push_back(v[j]);
j++;
}
for (int k = l; k < r; ++k) {
v[k] = result[k - l];
}
}
std::vector<int> Solve(int N) {
std::vector<int> T(N);
std::vector<int> cisla(N);
for (int i = 0; i < N; i++){
cisla[i] = i;
}
merge_sort(cisla, 0, N);
for (int i = 0; i + 2 < N; i++){
bool XY = Query(cisla[i], cisla[i+1]);
bool XZ = Query(cisla[i], cisla[i+2]);
if ((XZ && XY) || (!XZ && !XY)) {
std::swap(cisla[i], cisla[i+1]);
}
}
for (int i = N-1; i - 2 >= 0; i--) {
bool YZ = Query(cisla[i-1], cisla[i]);
bool XZ = Query(cisla[i-2], cisla[i]);
if ((XZ && YZ) || (!XZ && !YZ)) {
std::swap(cisla[i-1], cisla[i]);
}
}
for (int i = 0; i < N; i++){
T[cisla[i]] = i;
}
for (int i = 0; i < N; i++) T[i] = (N - 1) - T[i];
return T;
}
