#include "minerals.h" #include<bits/stdc++.h> using namespace std; #define pb push_back const int lim=5e4; int curval=0; int p[2*lim]; int query(int x){ return Query(p[x]+1); } int delta(int x){ int past=curval; curval=query(x); return curval-past; } void answer(int x,int y){ // cerr<<x<<' '<<y<<'\n'; Answer(p[x]+1,p[y]+1); } struct{ int tree[2*lim]; void update(int p,int val){ p+=5; while(p<2*lim){ tree[p]+=val; p+=p&-p; } } int query(int p){ p+=5; int ans=0; while(p){ ans+=tree[p]; p-=p&-p; } return ans; } int walk(int val){ int p=0; for(int i=20;0<=i;i--){ if(p+(1<<i)<2*lim&&tree[p+(1<<i)]<val){ val-=tree[p+(1<<i)]; p+=(1<<i); } } return p+1-5; } }fw; void Solve(int n) { srand(chrono::high_resolution_clock().now().time_since_epoch().count()); for(int i=0;i<2*n;i++){ p[i]=i; } random_shuffle(p,p+2*n); int l[2*n]{},r[2*n]{}; vector<int>down,up; for(int i=0;i<2*n;i++){ if(down.size()==n||!delta(i)){ up.pb(i); r[i]=down.size()-1; }else{ fw.update(down.size(),1); down.pb(i); } } int cnt=0,ty=0; while(cnt<n){ vector<int>v[n]; for(int tr=1;tr;){ tr=0; for(int i=0;i<n;i++){ if(l[up[i]]==-1){ continue; } l[up[i]]=fw.walk(fw.query(l[up[i]]-1)+1); r[up[i]]=fw.walk(fw.query(r[up[i]])); if(l[up[i]]==r[up[i]]){ answer(up[i],down[l[up[i]]]); fw.update(l[up[i]],-1); l[down[l[up[i]]]]=-1; l[up[i]]=-1; cnt++; tr=1; } } } for(int i=0;i<n;i++){ if(l[up[i]]==-1){ continue; } int mid=fw.walk(fw.query(l[up[i]])+fw.query(r[up[i]])>>1); v[mid].pb(i); } if(cnt==n)break; if(!ty){ for(int i=n-1;0<=i;i--){ for(int tr=1;tr;){ tr=0; for(int j:v[i]){ if(l[up[j]]==-1)continue; l[up[j]]=fw.walk(fw.query(l[up[j]]-1)+1); r[up[j]]=fw.walk(fw.query(r[up[j]])); if(l[up[j]]==r[up[j]]){ answer(up[j],down[l[up[j]]]); fw.update(l[up[j]],-1); l[down[l[up[j]]]]=-1; l[up[j]]=-1; cnt++; tr=1; } } } for(int j:v[i]){ if(l[up[j]]==-1)continue; l[up[j]]=fw.walk(fw.query(l[up[j]]-1)+1); r[up[j]]=fw.walk(fw.query(r[up[j]])); if(l[up[j]]==r[up[j]]){ answer(up[j],down[l[up[j]]]); fw.update(l[up[j]],-1); l[down[l[up[j]]]]=-1; l[up[j]]=-1; cnt++; continue; } int mid=fw.walk(fw.query(l[up[j]])+fw.query(r[up[j]])>>1); if(mid<i){ v[mid].pb(j); continue; } if(r[up[j]]<i||i<l[up[j]])continue; if(delta(up[j])){ l[up[j]]=i+1; }else{ r[up[j]]=i; } l[up[j]]=fw.walk(fw.query(l[up[j]]-1)+1); r[up[j]]=fw.walk(fw.query(r[up[j]])); if(l[up[j]]==r[up[j]]){ answer(up[j],down[l[up[j]]]); fw.update(l[up[j]],-1); l[down[l[up[j]]]]=-1; l[up[j]]=-1; cnt++; }else{ int mid=fw.walk(fw.query(l[up[j]])+fw.query(r[up[j]])>>1); v[mid].pb(j); } } if(i&&l[down[i]]!=-1){ delta(down[i]); } } }else{ for(int i=0;i<n;i++){ for(int tr=1;tr;){ tr=0; for(int j:v[i]){ if(l[up[j]]==-1)continue; l[up[j]]=fw.walk(fw.query(l[up[j]]-1)+1); r[up[j]]=fw.walk(fw.query(r[up[j]])); if(l[up[j]]==r[up[j]]){ answer(up[j],down[l[up[j]]]); fw.update(l[up[j]],-1); l[down[l[up[j]]]]=-1; l[up[j]]=-1; cnt++; tr=1; } } } if(i&&l[down[i]]!=-1){ delta(down[i]); } for(int j:v[i]){ if(l[up[j]]==-1)continue; l[up[j]]=fw.walk(fw.query(l[up[j]]-1)+1); r[up[j]]=fw.walk(fw.query(r[up[j]])); if(l[up[j]]==r[up[j]]){ answer(up[j],down[l[up[j]]]); fw.update(l[up[j]],-1); l[down[l[up[j]]]]=-1; l[up[j]]=-1; cnt++; continue; } int mid=fw.walk(fw.query(l[up[j]])+fw.query(r[up[j]])>>1); if(i<mid){ v[mid].pb(j); continue; } if(r[up[j]]<i||i<l[up[j]])continue; if(delta(up[j])){ l[up[j]]=i+1; }else{ r[up[j]]=i; } l[up[j]]=fw.walk(fw.query(l[up[j]]-1)+1); r[up[j]]=fw.walk(fw.query(r[up[j]])); if(l[up[j]]==r[up[j]]){ answer(up[j],down[l[up[j]]]); fw.update(l[up[j]],-1); l[down[l[up[j]]]]=-1; l[up[j]]=-1; cnt++; }else{ int mid=fw.walk(fw.query(l[up[j]])+fw.query(r[up[j]])>>1); v[mid].pb(j); } } } } ty^=1; } }

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:63:17: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = int*]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   63 |   random_shuffle(p,p+2*n);
      |   ~~~~~~~~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from minerals.cpp:2:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~