Submission #133261

#	Time	Username	Problem	Language	Result	Execution time	Memory
133261		ekrem	Minerals (JOI19_minerals)	C++17	40 / 100	192 ms	12364 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, a[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(*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(*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(*it2);
				if(don < onc)
					a.insert(*it2);
				onc = don;
			}
			Query(*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++){
		a[i] = i;
		s.insert(i);
	}
	coz(s, n/2);
	return;
	// random_shuffle(a + 1, a + n + 1, myrandom);
	// for(int i = 1; i <= n; i++)
	// 	cout << a[i] << " ";cout << endl;
	// n *= 2;
	for(int i = 1; i <= n; i++){
		top++;
		int don = top - Query(a[i]);
		cout << i << " " << don << endl;
		if(don == 2 and 0){
			for(int j = 1; j < i; j++){
				if(u[a[j]])
					continue;
				top--;
				int don = top - Query(a[j]);
				// cout << j << " " << don << endl;
				if(don == 1){
					for(int k = j - 1; k >= 1; k--)
						if(!u[a[k]]){
							top++;
							Query(a[k]);
						}
					u[a[j]] = u[a[i]] = 1;
					// cout << "Buldum " << i << " " << j << endl;
					Answer(a[i], a[j]);
					top--;
					Query(a[i]);
					break;
				}
			}
			// cout << "Bitti" << endl;
		}
	}
}

• 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