Submission #764356

#	Time	Username	Problem	Language	Result	Execution time	Memory
764356		Dan4Life	Minerals (JOI19_minerals)	C++17	85 / 100	47 ms	3816 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
int n;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int cur, pre;
bool Q(int i){ cur = Query(i); bool ok=(cur!=pre); pre=cur; return ok;}
 
void dnc(vector<int> l, vector<int> r, bool d){
    int n = sz(l); int m = max(1.0,n*0.4); if(n<1) return;
    if(n==1) return void(Answer(l[0],r[0])); 
    m = min(m,n-m);
    vector<int> v[2], w[2]; 
    for(int i : {0,1}) v[i].clear(), w[i].clear();
    for(int i = (d?0:m); i < (d?m:n); i++) Q(l[i]);
    for(int i = 0; i < n; i++) v[i>=m].pb(l[i]);
    shuffle(all(r),rng);
    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(v[0],w[0],0); dnc(v[1],w[1],1);
}
 
void Solve(int N) {
    vector<int> w[2];
    for(int i = 1; i <= 2*N; i++) w[Q(i)].pb(i);
    dnc(w[0],w[1],0);
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10