Submission #617273

#	Time	Username	Problem	Language	Result	Execution time	Memory
617273		errorgorn	Minerals (JOI19_minerals)	C++17	90 / 100	65 ms	9752 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 endl '\n'

#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 CURR=0;
int same(int x){
	int temp=Query(x);
	int res=CURR==temp;
	CURR=temp;
	return res;
}

int n;
int in[50005];
int mask[50005];

vector<ii> v;
int pos[70005];

vector<int> posi[70005];
vector<int> posi2[70005];
int done[70005];

void solve(vector<int> l,vector<int> r,int TOGGLE){
	int n=sz(l);
	v.clear();
	rep(x,0,70005) posi[x].clear();
	rep(x,0,70005) posi2[x].clear();
	memset(done,-1,sizeof(done));
	rep(x,0,n) in[x]=TOGGLE;
	rep(x,0,n) mask[x]=0;
	
	//for (auto it:l) cout<<it<<" "; cout<<endl;
	//for (auto it:r) cout<<it<<" "; cout<<endl;
	//cout<<TOGGLE<<endl<<endl;
	
	int s=0;
	while ((1<<s)<n) s++;
	
	rep(x,0,1<<s){
		int curr=0;
		int num=0;
		rep(bit,0,s){
			int temp=!!(x&(1<<bit));
			if (curr!=temp) num++;
			curr=temp;
		}
		v.pub({num,x});
	}
	
	sort(all(v));
	
	if (TOGGLE==1) for (auto &it:v) it.se^=(1<<s)-1;
	
	rep(x,0,sz(v)) pos[v[x].se]=x;
	
	int af=(1<<(s-1))-1;
	rep(x,0,n) posi[v[x].se&af].pub(v[x].se);
	rep(x,0,n) posi2[v[x].se&(af>>1)].pub(v[x].se);
	
	rep(bit,0,s){
		rep(x,0,n){
			int val=!!(v[x].se&(1<<bit));
			if (in[x]!=val) same(l[x]);
			in[x]=val;
		}
		
		rep(x,0,n){
			if (bit==s-1){
				if (sz(posi[mask[x]])==1){
					mask[x]=posi[mask[x]][0];
				}
				else if (done[mask[x]]==-1){
					if (same(r[x])){
						done[mask[x]]=0;
						mask[x]|=1<<bit;
					}
					else{
						done[mask[x]]=1;
					}
				}
				else{
					mask[x]|=done[mask[x]]<<bit;
				}
			}
			else{
				if (same(r[x])) mask[x]|=1<<bit;
			}
		}
	}
	
	rep(x,0,n) Answer(l[pos[mask[x]]],r[x]);
}

void Solve(signed N) {
	n=N;
	
	vector<int> idx;
	rep(x,1,2*n+1) idx.pub(x);
	shuffle(all(idx),rng);
	
	vector<int> l1,r1;
	vector<int> l2,r2;
	vector<int> l3,r3;
	
	rep(x,0,n){
		if (same(idx[x])) r1.pub(idx[x]);
		else l1.pub(idx[x]);
	}
	
	vector<int> temp;
	for (auto it:l1){
		if (same(it)) temp.pub(it);
		else l2.pub(it);
	}
	solve(r1,temp,1);
	
	rep(x,n,2*n){
		if (same(idx[x])) r3.pub(idx[x]);
		else l3.pub(idx[x]);
	}
	
	temp.clear();
	for (auto it:l3){
		if (same(it)) temp.pub(it);
		else r2.pub(it);
	}
	solve(r3,temp,1);
	
	solve(l2,r2,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: 5 / 5
• Subtask 9: 0 / 10