# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
764364 | 2023-06-23T11:10:02 Z | Dan4Life | Minerals (JOI19_minerals) | C++17 | 0 ms | 0 KB |
#include "minerals.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #define pb push_back #define sz(a) (int)a.size() int cur, pre; vi w[2]; bool Q(int i){ cur = Query(i); bool ok=(cur!=pre); pre=cur; return ok;} void dnc(vi l, vi r, bool d){ int n = sz(l); int m = max(1.0,n*0.4); if(n<1) return; if(n==1) return Answer(l[0],r[0]); if(!d) m=n-m; w={{},{}}; for(int i = (d?0:m); i < (d?m:n); i++) Q(l[i]); random_shuffle(begin(r),end(r)); for(int i : r){ if(sz(w[0])==m) w[1].pb(i); else if(sz(w[1])==n-m) w[0].pb(i); else w[Q(i)].pb(i); } dnc(vi(begin(l),begin(l)+m),w[0],0); dnc(vi(begin(l)+m,end(l)),w[1],1); } void Solve(int N) { for(int i = 1; i <= 2*N; i++) w[Q(i)].pb(i); dnc(w[0],w[1],0); }