#include "minerals.h" #include <vector> #include <iostream> #include <algorithm> using namespace std; using vi = vector<int>; const int maxN = 43'000; int N; vi mushroom(1+2*maxN, 0); int last_ans = 0; int sz(vi x) { return int(x.size()); } void dnc(vi L, vi R, bool bL, bool bR) { // cerr << "dnc " << b << " : "; // for(int l:L) cerr << l << ' '; // cerr << " | "; // for(int r:R) cerr << r << ' '; // cerr << "\n"; if(int(L.size()) == 1) Answer(L[0], R[0]); else if(int(L.size()) == 2) { if(!bL) last_ans = Query(L[0]); else last_ans = Query(L[1]); //0 is active int prev_ans = last_ans; last_ans = Query(R[0]); if(prev_ans == last_ans) { Answer(L[0], R[0]); Answer(L[1], R[1]); } else { Answer(L[0], R[1]); Answer(L[1], R[0]); } } else { int K = int(L.size()); vi L1, L2; for(int i = 0; i < K/2; i++) L1.push_back(L[i]); for(int i = K/2; i < K; i++) L2.push_back(L[i]); if(bL) { for(int l: L2) last_ans = Query(l); } else { for(int l: L1) last_ans = Query(l); } vi R1, R2; for(int r:R) { if(sz(R1) == sz(L1) && sz(R2) + 1 == sz(L2)) { R2.push_back(r); } else if(sz(R1) + 1 == sz(L1) && sz(R2) == sz(L2)) { R1.push_back(r); } else { int prev_ans = last_ans; last_ans = Query(r); if(last_ans == prev_ans) { R1.push_back(r); } else { R2.push_back(r); } } } dnc(L1, R1, 1, !bR); dnc(L2, R2, 0, !bR); } } void Solve(int N_) { N = N_; int ct = 0; for(int i = 1; i <= 2*N; i++) { last_ans = Query(i); if(last_ans > ct) { // cerr << "increasing ct = " << ct << " at " << i << '\n'; ct++; mushroom[i] = ct; // cerr << i << " : " << mushroom[i] << '\n'; } } // cerr << "check\n"; // for(int i = 1; i <= 2*N; i++) cerr << i << " : " << mushroom[i] << '\n'; vi leftval, rightval; for(int i = 1; i <= 2*N; i++) { if(mushroom[i]) leftval.push_back(i); else rightval.push_back(i); } dnc(leftval, rightval, 1, 1); }