#include "monster.h" #include<bits/stdc++.h> using namespace std; int n; namespace sub1{ vector<int>solve(){ vector<int>ans(n, 0); for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ ans[Query(i, j) ? i : j]++; } } for(int i = 0, small = -1, large = -1; i < n; i++){ if(ans[i] == 1){ if(small == -1){ small = i; } else{ ans[i] = 1 ^ (ans[small] = (Query(small, i) ? 0 : 1)); } } else if(ans[i] == n - 2){ if(large == -1){ large = i; } else{ ans[i] = (n - 2) ^ (n - 1) ^ (ans[large] = (Query(large, i) ? n - 2 : n - 1)); } } } return ans; } } namespace sub23{ const int lim = 1e3 + 5; int cache[lim][lim]; bool ask(int i, int j){ bool z = i > j; if(z){ swap(i, j); } int& ans = cache[i][j]; if(ans != -1){ return ans ^ z; } return (ans = Query(i, j)) ^ z; } vector<int>p; int find_zero(){ vector<pair<int, int>>cnt(min(n, 8), make_pair(0, 0)); for(int i = 0; i < min(n, 8); i++){ for(int j = i + 1; j < min(n, 8); j++){ cnt[ask(p[i], p[j]) ? i : j].first++; } cnt[i].second = p[i]; } sort(cnt.begin(), cnt.end()); return cnt[ask(cnt[1].second, cnt[0].second)].second; } vector<int>merge_sort(vector<int>p){ if(p.size() < 2){ return p; } int m = int(p.size()) >> 1; vector<int>a = merge_sort(vector<int>(p.begin(), p.begin() + m)), b = merge_sort(vector<int>(p.begin() + m, p.end())), ans(p.size()); merge(a.begin(), a.end(), b.begin(), b.end(), ans.begin(), [&] (int i, int j){ return !ask(i, j); }); return ans; } vector<int>solve(){ memset(cache, -1, sizeof(cache)); p.resize(n); iota(p.begin(), p.end(), 0); p = merge_sort(p); vector<int>cur, ans(1, find_zero()); for(int i = 0; i < n; i++){ if(p[i] != ans[0]){ cur.push_back(p[i]); if(ask(ans.back(), p[i])){ while(!cur.empty()){ ans.push_back(cur.back()); cur.pop_back(); } } } } while(!cur.empty()){ ans.push_back(cur.back()); cur.pop_back(); } vector<int>ret(n); for(int i = 0; i < n; i++){ ret[ans[i]] = i; } return ret; } } vector<int>Solve(int _n){ if((n = _n) <= 200){ return sub1::solve(); } return sub23::solve(); }