#include <iostream> #include <vector> #include <random> #include <chrono> #include <algorithm> #include "grader.h" using namespace std; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); const int N = 500; int seen[N], p[N], num; int ask(vector<int> v, int i, int j){ num++; // if (num > 20) // exit(0); swap(v[i], v[j]); i = query(v); if (i == v.size()) exit(0); return query(v); } void solve(int n){ vector<int> ind, val; for (int i=0;i<n;i++){ ind.push_back(i); val.push_back(i+1); } // shuffle(begin(val), end(val), rnd); int cur = ask(val, 1, 1); while (cur < n){ // cout<<cur<<endl; while (ind.size() > 0 and seen[ind[0]]) ind.erase(begin(ind)); for (int i=1;i<ind.size();i++){ if (seen[ind[0]] or seen[ind[i]]) continue; int cur1 = ask(val, ind[0], ind[i]); if (cur1 == cur) continue; if (cur1 == cur - 2){ seen[ind[0]] = seen[ind[i]] = 1; } else if (cur1 == cur + 2){ seen[ind[0]] = seen[ind[i]] = 1; swap(val[ind[0]], val[ind[i]]); cur += 2; } else if (cur1 == cur - 1){ int j = 0; if (ind[0] == j or ind[i] == j) j++; if (ind[0] == j or ind[i] == j) j++; if (seen[j]){ if (ask(val, ind[0], j) == cur - 2) seen[ind[0]] = 1; else seen[ind[i]] = 1; } else{ int cur2 = ask(val, ind[0], j), cur3 = ask(val, ind[i], j); if (cur2 == cur or cur2 == cur - 1 and cur3 == cur - 2) seen[ind[i]] = 1; else seen[ind[0]] = 1; } } else{ swap(val[ind[0]], val[ind[i]]); cur++, i--; } } if (seen[ind[0]] == 0) return; } }