#include <bits/stdc++.h> #include "minerals.h" using namespace std; typedef long long ll; typedef double dl; typedef vector<int> vi; typedef vector<vector<int>> vii; typedef vector<ll> vl; typedef vector<bool> vb; typedef pair<int,int> pii; typedef pair<ll, ll> pll; #define ff first #define ss second #define all(a) a.begin(),a.end() #define gcd(a,b) __gcd(a,b) #define lcm(a,b) (a*(b/gcd(a,b))) #define file(); freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout); #define spc " " #ifdef ONLINE_JUDGE #define debarr(array) #define deb(x) #else #define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl; #define deb(x) cerr << #x << " = " << x << endl; #endif const double PI = acos(-1); const int MOD = 1000000007; const int inf = (2147483647); const double EPS = 1e-6; const int MAXN = 1e5+10; const int NONE = 0; const int FF = 1; const int SS = 2; const int ALL = 3; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void Solve(int N) { int n = N*2; vector<vii> arr((N+10)*20, vii(2)); int idx = 0, pushTo = 0; int last = 0; for(int i = 1; i <= n; i++){ int now = Query(i); if(now==last){ arr[pushTo][1].push_back(i); }else{ arr[pushTo][0].push_back(i); last = now; } } pushTo++; // Took 2N operations // Two group differented stack<pii> order; order.push({0, ALL}); int count = 0; while(!order.empty()){ count++; // deb(order.top().ff) // deb(order.top().ss) vii x = arr[order.top().ff]; int gone = order.top().ss; order.pop(); // debarr(x[0]) cerr << endl; // debarr(x[1]) cerr << endl << endl; int sz = x[0].size(); if(sz<=1) continue; int m = (sz)/2; if(gone==ALL){ for(int i = 0; i < m; i++) arr[pushTo][0].push_back(x[0][i]); for(int i = m; i < sz; i++) last = Query(x[0][i]), arr[pushTo+1][0].push_back(x[0][i]); for(auto y: x[1]){ int now = Query(y); if(now==last){ arr[pushTo][1].push_back(y); }else{ arr[pushTo+1][1].push_back(y); } last = now; } order.push({pushTo, FF}); order.push({pushTo+1, NONE}); }else if(gone==FF){ for(int i = 0; i < m; i++) arr[pushTo][0].push_back(x[0][i]); for(int i = m; i < sz; i++) last = Query(x[0][i]), arr[pushTo+1][0].push_back(x[0][i]); for(auto y: x[1]){ int now = Query(y); if(now==last){ arr[pushTo][1].push_back(y); }else{ arr[pushTo+1][1].push_back(y); } last = now; } order.push({pushTo, ALL}); order.push({pushTo+1, SS}); }else if(gone==SS){ for(int i = 0; i < m; i++) arr[pushTo][0].push_back(x[1][i]); for(int i = m; i < sz; i++) last = Query(x[1][i]), arr[pushTo+1][0].push_back(x[1][i]); for(auto y: x[0]){ int now = Query(y); if(now==last){ arr[pushTo][1].push_back(y); }else{ arr[pushTo+1][1].push_back(y); } last = now; } order.push({pushTo, ALL}); order.push({pushTo+1, SS}); }else{ for(int i = 0; i < m; i++) arr[pushTo][0].push_back(x[0][i]); for(int i = m; i < sz; i++) last = Query(x[0][i]), arr[pushTo+1][0].push_back(x[0][i]); for(auto y: x[1]){ int now = Query(y); if(now==last){ arr[pushTo+1][1].push_back(y); }else{ arr[pushTo][1].push_back(y); } last = now; } order.push({pushTo, SS}); order.push({pushTo+1, ALL}); } pushTo+=2; } for(auto x: arr){ if(x[0].size()==1){ Answer(x[0][0], x[1][0]); } } // deb(count) return; }