Submission #133267

#	Time	Username	Problem	Language	Result	Execution time	Memory
133267		ekrem	Minerals (JOI19_minerals)	C++14	40 / 100	227 ms	12580 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define MAXN 1000005
using namespace std;
 
typedef long long ll;
typedef pair < int , int > ii;
typedef set < int > si;
 
int n, top = 1, aa[MAXN], u[MAXN];
si s;
si :: iterator it, it2;
 
int myrandom(int x){
	return rand()%x;
}
 
void coz(si s, int x){
	if((int)s.size() == 2){
		vector < int > x;
		for(it = s.begin(); it != s.end(); it++)
			x.pb(aa[*it]);
		Answer(x[0], x[1]);
		return;
	}
	si a;
	int top = 0, onc = 0, don;
	for(it = s.begin(); it != s.end(); it++){
		top++;
		don = top - Query(aa[*it]);
		// cout << *it << " " << don << endl;
		if(don > onc)
			a.insert(*it);
		onc = don;
		if(don >= x/2){
			// cout << "Burda BOL" << endl;
			for(it2 = s.begin(); it2 != it; it2++){
				top--;
				don = top - Query(aa[*it2]);
				if(don < onc)
					a.insert(*it2);
				onc = don;
			}
			Query(aa[*it]);
			break;
		}
	}
	for(it = a.begin(); it != a.end(); it++){
		// cout << *it << endl;
		s.erase(*it);
	}
	coz(a, x/2);
	coz(s, x - x/2);
}
 
void Solve(int n) {n*= 2;
	srand(time(0));
	::n = n;
 
 
 
	for(int i = 1; i <= n; i++){
		aa[i] = i;
		s.insert(i);
	}
	random_shuffle(aa + 1, aa + n + 1, myrandom);
	// for(int i = 1; i <= n; i++)
	// 	cout << aa[i] << " ";cout << endl;
	coz(s, n/2);
	return;
}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10