Submission #764359

#	Time	Username	Problem	Language	Result	Execution time	Memory
764359		Dan4Life	Minerals (JOI19_minerals)	C++17	100 / 100	53 ms	3920 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()

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 Answer(l[0],r[0]); 
    if(!d) 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]);
    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(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);
}

Compilation message (stderr)

minerals.cpp: In function 'void dnc(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:13:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   13 |     if(!d) m=n-m; vector<int> v[2], w[2];
      |     ^~
minerals.cpp:13:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   13 |     if(!d) m=n-m; vector<int> v[2], w[2];
      |                   ^~~~~~

• 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: 5 / 5
• Subtask 9: 10 / 10