#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> typedef long long ll; typedef long double ld; using namespace __gnu_pbds; using namespace std; #include "minerals.h" template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; int cnt = 0; bool put(int x) { int ocnt = cnt; cnt = Query(x); return cnt!=ocnt; } void cdq(vector<int> L, vector<int> R, bool l) { int n = L.size(); if(n==1) { Answer(L[0], R[0]); return; } ld r = 0.4; int m = ceil(n * r); if(m==0) m=1; if(m==n) m=n-1; vector<int> L1, L2; for(int i=0; i<m; ++i) L1.push_back(L[i]); for(int i=m; i<n; ++i) L2.push_back(L[i]); if(l) { for(int i=m; i<n; ++i) put(L[i]); } else for(int i=0; i<m; ++i) put(L[i]); vector<int> R1, R2; for(int i=0; i<R.size(); ++i) { if(put(R[i])) R2.push_back(R[i]); else R1.push_back(R[i]); if(R1.size()==L1.size()) { for(int j=i+1; j<R.size(); ++j) R2.push_back(R[j]); break; } if(R2.size()==L2.size()) { for(int j=i+1; j<R.size(); ++j) R1.push_back(R[j]); break; } } cdq(L1, R1, 1); cdq(L2, R2, 0); } void Solve(int N) { vector<int> L; vector<int> R; vector<int> kolej; for(int i=1; i<=2*N; ++i) kolej.push_back(i); for(auto i : kolej) { if(put(i)) L.push_back(i); else R.push_back(i); } random_device rd; mt19937 gen(rd()); shuffle(L.begin(), L.end(), gen); shuffle(R.begin(), R.end(), gen); cdq(L, R, 1); }