# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
764364 | Dan4Life | Minerals (JOI19_minerals) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
}