Submission #488198

#	Time	Username	Problem	Language	Result	Execution time	Memory
488198		PixelCat	Minerals (JOI19_minerals)	C++14	100 / 100	38 ms	2544 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
#define For(i,a,b)    for(int i=a;i<=b;i++)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())

bool toggle(int x){
	static int last=0;
	int now=Query(x);
	bool ans=(now==last);
	last=now;
	return ans;
}

void solve(vector<int> &vl,vector<int> &vr,int l,int r,bool fill){
	if(sz(vl)==1){
		Answer(vl[0],vr[l]);
		return;
	}
	int n=max(1,sz(vl)/3);
	int m=sz(vl)-n;
	For(i,l,l+n-1) toggle(vr[i]);
	vector<int> vll,vlr;
	for(auto &i:vl){
		if(sz(vll)==n) vlr.eb(i);
		else if(sz(vlr)==m) vll.eb(i);
		else{
			bool res=toggle(i);
			if(fill!=res) vll.eb(i);
			else vlr.eb(i);
		}
	}
	solve(vll,vr,l,l+n-1,!fill);
	solve(vlr,vr,l+n,r,fill);
}

void Solve(int32_t n){
	vector<int> l,r;
	For(i,1,n*2){
		if(toggle(i)) l.eb(i);
		else r.eb(i);
	}
	random_shuffle(all(r));
	solve(l,r,0,n-1,true);
}

• 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