#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> Solve(int N) {
int query_count = 0;
map<pair<int, int>, int> memo;
const auto Compare = [&](int a, int b) {
if (memo.count({a, b})) return memo[{a, b}];
query_count++;
int foo = Query(a, b);
memo[{a, b}] = foo;
memo[{b, a}] = 1 - foo;
return foo;
};
const auto MergeSort = [&](const auto &self, int l, int r) -> vector<int> {
// S result will look like: [6 7 8][3 4 5][1 2]
// Groups of consecutive elements i, i+1, ..., sorted decreasingly
// There are no adjacent groups with both size 1
// There are at least 2 groups
if (l == r) return {l};
int md = (l + r) / 2;
vector<int> lft = self(self, l, md);
vector<int> rgt = self(self, md + 1, r);
vector<int> res;
reverse(begin(lft), end(lft));
reverse(begin(rgt), end(rgt));
while (!lft.empty() && !rgt.empty()) {
if (Compare(lft.back(), rgt.back())) {
res.emplace_back(lft.back());
lft.pop_back();
} else {
res.emplace_back(rgt.back());
rgt.pop_back();
}
}
while (!lft.empty()) {
res.emplace_back(lft.back());
lft.pop_back();
}
while (!rgt.empty()) {
res.emplace_back(rgt.back());
rgt.pop_back();
}
return res;
};
vector<int> almostSorted = MergeSort(MergeSort, 0, N - 1);
// If we can find maximum element in almostSorted[], we can recover the sorted[] easily
// Just, from maximum element, sweep to front. Delete all involved.
// Then, from first elements, we sweep until we hit a false query. This must be
// the second maximum elements, so we can recurse.
//
// How to find maximum element?
// For first element, go sweep until we hit WRONG 2 times. Then, first element must not
// be maximum. Continue from the first time we hit WRONG.
//
// Then, if we only hit WRONG once, it is either max or second max. The one which is WRONG
// must be current-1. Check whether the one which is wrong is max or second max (WRONG occurs
// once). If it is, then by the structure of almostSorted[], then current must be max.
//
// If current is second max, we must find max. But due to the structure of almostSorted[],
// the next element after current must be max.
//
// So we need 2N queries to identify max, and an additional N queries to get sort[].
// This gets 92-94 points.
//
// Note that, using the merge sort takes at most 8977 queries (\sum_{i = 1}^{1000} ceil(log2(i))).
// Alternatively: N log N - N.
// Now we have 1023 queries left to identify sorted[].
//
// Of those 1023 queries, we need 1000 to construct sorted[]. Through casebashing,
// we need around N + constant queries to find max and recover sorted[]. Thus the total
// number of queries <= 10000.
//
// Total queries: N log N.
const auto FindMaxSpecial = [&](int start) -> int {
// find max in almostSorted[start...]
// assuming almostSorted[start, start + 2] is in a group
for (int i = start + 1; i + 2 < N; i++) {
if (Compare(almostSorted[i], almostSorted[i + 2])) {
// looks like: 4 5 0 (Compare 4 <-> 0)
// Compare(x, x - 1) will never occur
return i + 1;
}
}
// everything in 1 group
return N - 1;
};
vector<int> sorted;
vector<int> done(N);
int mxId = -1;
int last = 0;
if (Compare(almostSorted[0], almostSorted[2])) {
// - 3 4 1 2 ..
// - 3 0 1 2 ..
if (Compare(almostSorted[1], almostSorted[3])) {
mxId = 1;
} else {
mxId = 0;
}
} else {
// - 3 4 5 6 ...
// - 3 4 5 2 ...
// - 3 4 5 0 ...
// - 3 1 2 0 ...
// - 3 4 2 0 ...
if (Compare(almostSorted[0], almostSorted[3])) {
// - 3 4 5 0 ...
// - 3 1 2 0 ...
// - 3 4 2 0 ...
if (Compare(almostSorted[1], almostSorted[3])) {
// - 3 4 5 0 1
// - 3 4 5 1 2 ...
// - 3 4 2 0 1 ...
// - 4 5 3 0 1 ...
// - 4 2 3 0 1 ...
assert(N >= 5);
if (!Compare(almostSorted[1], almostSorted[4])) {
// - 5 3 4 1 2 ...
mxId = 4;
last = 3;
done[0] = done[1] = done[2] = 1;
sorted.emplace_back(almostSorted[0]);
sorted.emplace_back(almostSorted[2]);
sorted.emplace_back(almostSorted[1]);
} else if (Compare(almostSorted[2], almostSorted[4])) {
// - 3 4 5 0 1 ...
// - 3 4 5 1 2 ...
// - 4 5 3 0 1 ...
// - 5 3 4 0 1 ...
if (Compare(almostSorted[0], almostSorted[4])) {
// - 3 4 5 0 1 2 ...
// - 4 5 3 0 1 2 ...
// - 5 3 4 0 1 2 ...
assert(N >= 6);
last = 3;
mxId = FindMaxSpecial(3);
if (!Compare(almostSorted[0], almostSorted[mxId])) {
// - 3 4 5 0 1 2 ...
done[0] = done[1] = done[2] = 1;
sorted.emplace_back(almostSorted[2]);
sorted.emplace_back(almostSorted[1]);
sorted.emplace_back(almostSorted[0]);
} else if (!Compare(almostSorted[1], almostSorted[mxId])) {
// - 5 3 4 0 1 2 ...
done[0] = done[1] = done[2] = 1;
sorted.emplace_back(almostSorted[0]);
sorted.emplace_back(almostSorted[2]);
sorted.emplace_back(almostSorted[1]);
} else if (!Compare(almostSorted[2], almostSorted[mxId])) {
// - 4 5 3 0 1 2 ...
done[0] = done[1] = done[2] = 1;
sorted.emplace_back(almostSorted[1]);
sorted.emplace_back(almostSorted[0]);
sorted.emplace_back(almostSorted[2]);
}
} else {
// - 3 4 5 1 2 ...
mxId = 2;
}
} else {
// - 3 4 2 0 1 ...
mxId = 1;
}
} else {
// - 3 1 2 0 ...
mxId = 0;
}
} else {
// - 3 4 5 6 ...
// - 3 4 5 2 ...
mxId = FindMaxSpecial(0);
}
}
for (int i = mxId; i >= 0; i--) if (!done[i]) {
done[i] = 1;
sorted.emplace_back(almostSorted[i]);
}
for (int i = mxId + 1; i < N; i++) {
if (!Compare(almostSorted[last], almostSorted[i])) {
last = i;
while (!done[last]) {
done[last] = 1;
sorted.emplace_back(almostSorted[last]);
last--;
}
last++;
}
}
assert(sorted.size() == N);
vector<int> ans(N);
for (int i = 0; i < N; i++) {
ans[sorted[i]] = i;
}
for (int i = 0; i < N; i++) {
ans[i] = N - 1 - ans[i];
}
return ans;
}
