Submission #133765

#	Time	Username	Problem	Language	Result	Execution time	Memory
133765		hamzqq9	Minerals (JOI19_minerals)	C++14	90 / 100	98 ms	3460 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;

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

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

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

	}

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

		if(on[i]) 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;

	make(l,mid,r);

	vector<int> lcd,rcd;

	bool tol=0,tor=0;

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

	for(auto x:cd) {

		if(tol) {lcd.pb(x);continue ;}
		if(tor) {rcd.pb(x);continue ;}

		int cur=Query(p[x]);

		if(cnt!=cur) {

			rcd.pb(x);

		}
		else {

			lcd.pb(x);

		}

		cnt=cur;

		if(sz(lcd)==mid-l+1) tor=1;
		if(sz(rcd)==r-mid) tol=1;

	}

	solve(l,mid,lcd);
	solve(mid+1,r,rcd);

}

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