#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
int n;
void sort_slow(vector<int> &els, bool hasLeft, bool hasRight) {
int sz = els.size();
vector<int> a(sz, -1);
vector<int> loss(sz, 0), win(sz, 0);
int idxa = -1, idxb = -1;
int i2 = -1, j2 = -1;
vector<int> b4(sz+1, -1);
for (int i = 0; i < sz; i++) {
for (int j = i + 1; j < sz; j++) {
int ans = Query(els[i], els[j]);
if (ans == true) {
win[i]++;
loss[j]++;
}
else {
loss[i]++;
win[j]++;
}
}
a[i] = abs(loss[i] - sz) - 1;
if (a[i] == 1 + hasLeft) {
if (idxa == -1) idxa = i;
else idxb = i;
}
if (a[i] == sz-2 - hasRight) {
if (i2 == -1) i2 = i;
else j2 = i;
}
}
cout << "ORDER BEFORE: ";
for (int i = 0; i < sz; i++) cout << a[i] << " ";
if (idxa != -1 && idxb != -1) {
int ans = Query(els[idxa], els[idxb]);
if (ans) {
a[idxa] = 0 + hasLeft;
}
else a[idxb] = 0 + hasLeft;
}
if (i2 != -1 && j2 != -1) {
int ans = Query(els[i2], els[j2]);
if (ans) {
a[j2] = sz-1-hasRight;
}
else a[i2] = sz-1-hasRight;
}
cout << "ORDER: ";
for (int i = 0; i < sz; i++) cout << a[i] << " ";
cout << "\n";
vector<int> fin(sz);
for (int i = 0; i < sz; i++) {
fin[a[i]] = els[i];
}
els = fin;
}
vector<int> quick_select(vector<int> curr, bool hasLeft = false, bool hasRight = false) {
if (curr.size() <= 10) {
sort_slow(curr, hasLeft, hasRight);
return curr;
}
int sz = curr.size();
vector<int> small, large;
int el;
while (small.size() <= 2 || large.size() <= 2) {
el = curr[rand() % sz];
small.clear();
large.clear();
for (auto x: curr) {
if (x == el) continue;
if (Query(el, x)) {
small.push_back(x);
}
else large.push_back(x);
}
}
cout << el << "\n";
for (auto x: small) cout << x << " ";
cout << "\n";
for (auto x: large) cout << x << " ";
cout << "\n";
vector<int> fin;
small = quick_select(small, hasLeft, true);
large = quick_select(large, true, hasRight);
for (auto x: small) cout << x << " ";
cout << "\n";
for (auto x: large) cout << x << " ";
cout << "\n";
swap(small.back(), large[0]);
small.push_back(el);
for (auto x: large) small.push_back(x);
return small;
}
vector<int> Solve(int N) {
n = N;
vector<int> curr;
for (int i = 0; i < n; i++) curr.push_back(i);
vector<int> fin = quick_select(curr);
vector<int> ans(n);
for (int i = 0; i < n; i++) {
ans[fin[i]] = i;
}
for (int i = 0; i < n; i++) cout << fin[i] << " ";
cout << "\n";
return ans;
}
