Submission #133781

#	Time	Username	Problem	Language	Result	Execution time	Memory
133781		hamzqq9	Minerals (JOI19_minerals)	C++14	90 / 100	108 ms	3440 KiB

minerals

#include "minerals.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 2000000000000000
#define N 500005
#define MOD 998244353
#define KOK 700		
using namespace std;

vector<int> A,B;
vector<int> p;
vector<int> on;
int cnt;

mt19937 rnd;

int get(int l,int mid,int r,int ss) {

	int tot=0;

	for(int i=l;i<=mid;i++) {

		if(!(on[i]^ss)) tot++;

	}

	for(int i=mid+1;i<=r;i++) {

		if((on[i]^ss)) tot++;

	}

	return tot;

}

void make(int l,int mid,int r,int ss) {

	for(int i=l;i<=mid;i++) {

		if(!(on[i]^ss)) cnt=Query(p[A[i]]),on[i]=!on[i];

	}

	for(int i=mid+1;i<=r;i++) {

		if((on[i]^ss)) cnt=Query(p[A[i]]),on[i]=!on[i];

	}

}

void solve(int l,int r,vector<int> cd) {

	if(l==r) {

		for(auto x:cd) Answer(p[x],p[A[l]]);

		return ;

	}

	int mid=(l+r)>>1;

	int sw=0;
	int sz[2]={mid-l+1,r-mid};

	int tot[2]={0,0};

	tot[0]=get(l,mid,r,0);
	tot[1]=get(l,mid,r,1);

	if(tot[1]<tot[0]) {
		
		make(l,mid,r,1);
		sw=1;
		swap(sz[0],sz[1]);

	} else  make(l,mid,r,0);


	vector<int> go[2];
	bool to[2]={0,0};

	shuffle(cd.begin(),cd.end(),rnd);

	for(auto x:cd) {

		if(to[0]) {go[0].pb(x);continue ;}
		if(to[1]) {go[1].pb(x);continue ;}

		int cur=Query(p[x]);

		if(cnt!=cur) {

			go[1].pb(x);

		}
		else {

			go[0].pb(x);

		}

		cnt=cur;

		if(sz(go[0])==sz[0]) to[1]=1;
		if(sz(go[1])==sz[1]) to[0]=1;

	}

	if(sw) swap(go[0],go[1]);

	solve(l,mid,go[0]);
	solve(mid+1,r,go[1]);

}

void Solve(int n) {
 
	n<<=1;
 
	rnd=mt19937(time(NULL));
 
 	on=vector<int>(n,0);

	for(int i=1;i<=n;i++) p.pb(i);
 
	shuffle(p.begin(),p.end(),rnd);

	bool toA=0,toB=0;
	
	for(int i=0;i<n;i++) {
 
		if(toA) {A.pb(i);continue ;}
		if(toB) {B.pb(i);continue ;}		

		int cur=Query(p[i]);

		on[i]=!on[i];
 
		if(cur>cnt) {
 
			A.pb(i);
			
		}
		else {

			B.pb(i);
 
		}

		if(sz(A)==n/2) toB=1;
		if(sz(B)==n/2) toA=1;
 
		cnt=cur;
 
	}
	
	solve(0,sz(A)-1,B);
 
}

• 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