Submission #617882

#	Time	Username	Problem	Language	Result	Execution time	Memory
617882		errorgorn	Minerals (JOI19_minerals)	C++17	100 / 100	442 ms	6888 KiB

minerals

#include "minerals.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int num[50005];
int best[50005];

int CURR=0;
bool same(int x){
	int temp=Query(x);
	int res=CURR==temp;
	CURR=temp;
	return res;
}

int n;

void solve(vector<int> l,vector<int> r,bool in){
	int n=sz(l);
	if (n==0) return;
	
	if (n==1){
		Answer(l[0],r[0]);
	}
	else{
		vector<int> l1,l2;
		vector<int> r1,r2;
		
		rep(x,0,best[n]) l1.pub(l[x]);
		rep(x,best[n],n) l2.pub(l[x]);
		
		for (auto it:l1) same(it);
		for (auto it:r){
			if (sz(l1)==sz(r1)) r2.pub(it);
			else if (sz(l2)==sz(r2)) r1.pub(it);
			else if (same(it) != in) r1.pub(it);
			else r2.pub(it);
		}
		
		solve(l1,r1,!in);
		solve(l2,r2,in);
	}
}

vector<int> get(vector<int> v){
	vector<int> l,r;
	rep(x,0,sz(v)){
		if (same(v[x])) r.pub(v[x]);
		else l.pub(v[x]);
	}
	
	vector<int> good,bad;
	for (auto it:l){
		if (same(it)) good.pub(it);
		else bad.pub(it);
	}
	
	solve(good,r,false);
	return bad;
}

void Solve(signed N) {
	num[1]=0;
	rep(x,2,50005){
		num[x]=1e9;
		int l=max(1LL,(int)(x*0.25)),r=min(x,(int)(x*0.4)+2);
		
		rep(y,l,r) if (num[x]>num[y]+num[x-y]+x+y){
			num[x]=num[y]+num[x-y]+x+y;
			best[x]=y;
		}
	}
	
	n=N;
	
	vector<int> idx;
	rep(x,1,2*n+1) idx.pub(x);
	shuffle(all(idx),rng);
	
	vector<int> l,r;
	rep(x,0,n) l.pub(idx[x]);
	rep(x,n,2*n) r.pub(idx[x]);
	
	solve(get(l),get(r),false);
}

• 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