답안 #133261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133261	2019-07-20T10:12:59 Z	ekrem	Minerals (JOI19_minerals)	C++17	40 / 100	192 ms	12364 KB

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.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	636 KB	Output is correct
2	Correct	13 ms	1016 KB	Output is correct
3	Correct	23 ms	1668 KB	Output is correct
4	Correct	49 ms	2808 KB	Output is correct
5	Correct	102 ms	4984 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	6 ms	636 KB	Output is correct
6	Correct	13 ms	1016 KB	Output is correct
7	Correct	23 ms	1668 KB	Output is correct
8	Correct	49 ms	2808 KB	Output is correct
9	Correct	102 ms	4984 KB	Output is correct
10	Correct	6 ms	632 KB	Output is correct
11	Correct	68 ms	3496 KB	Output is correct
12	Correct	104 ms	5132 KB	Output is correct
13	Correct	72 ms	5140 KB	Output is correct
14	Correct	87 ms	5160 KB	Output is correct

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	6 ms	636 KB	Output is correct
6	Correct	13 ms	1016 KB	Output is correct
7	Correct	23 ms	1668 KB	Output is correct
8	Correct	49 ms	2808 KB	Output is correct
9	Correct	102 ms	4984 KB	Output is correct
10	Correct	6 ms	632 KB	Output is correct
11	Correct	68 ms	3496 KB	Output is correct
12	Correct	104 ms	5132 KB	Output is correct
13	Correct	72 ms	5140 KB	Output is correct
14	Correct	87 ms	5160 KB	Output is correct
15	Incorrect	192 ms	12364 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	6 ms	636 KB	Output is correct
6	Correct	13 ms	1016 KB	Output is correct
7	Correct	23 ms	1668 KB	Output is correct
8	Correct	49 ms	2808 KB	Output is correct
9	Correct	102 ms	4984 KB	Output is correct
10	Correct	6 ms	632 KB	Output is correct
11	Correct	68 ms	3496 KB	Output is correct
12	Correct	104 ms	5132 KB	Output is correct
13	Correct	72 ms	5140 KB	Output is correct
14	Correct	87 ms	5160 KB	Output is correct
15	Incorrect	192 ms	12364 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	6 ms	636 KB	Output is correct
6	Correct	13 ms	1016 KB	Output is correct
7	Correct	23 ms	1668 KB	Output is correct
8	Correct	49 ms	2808 KB	Output is correct
9	Correct	102 ms	4984 KB	Output is correct
10	Correct	6 ms	632 KB	Output is correct
11	Correct	68 ms	3496 KB	Output is correct
12	Correct	104 ms	5132 KB	Output is correct
13	Correct	72 ms	5140 KB	Output is correct
14	Correct	87 ms	5160 KB	Output is correct
15	Incorrect	192 ms	12364 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	6 ms	636 KB	Output is correct
6	Correct	13 ms	1016 KB	Output is correct
7	Correct	23 ms	1668 KB	Output is correct
8	Correct	49 ms	2808 KB	Output is correct
9	Correct	102 ms	4984 KB	Output is correct
10	Correct	6 ms	632 KB	Output is correct
11	Correct	68 ms	3496 KB	Output is correct
12	Correct	104 ms	5132 KB	Output is correct
13	Correct	72 ms	5140 KB	Output is correct
14	Correct	87 ms	5160 KB	Output is correct
15	Incorrect	192 ms	12364 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	6 ms	636 KB	Output is correct
6	Correct	13 ms	1016 KB	Output is correct
7	Correct	23 ms	1668 KB	Output is correct
8	Correct	49 ms	2808 KB	Output is correct
9	Correct	102 ms	4984 KB	Output is correct
10	Correct	6 ms	632 KB	Output is correct
11	Correct	68 ms	3496 KB	Output is correct
12	Correct	104 ms	5132 KB	Output is correct
13	Correct	72 ms	5140 KB	Output is correct
14	Correct	87 ms	5160 KB	Output is correct
15	Incorrect	192 ms	12364 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	248 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	6 ms	636 KB	Output is correct
6	Correct	13 ms	1016 KB	Output is correct
7	Correct	23 ms	1668 KB	Output is correct
8	Correct	49 ms	2808 KB	Output is correct
9	Correct	102 ms	4984 KB	Output is correct
10	Correct	6 ms	632 KB	Output is correct
11	Correct	68 ms	3496 KB	Output is correct
12	Correct	104 ms	5132 KB	Output is correct
13	Correct	72 ms	5140 KB	Output is correct
14	Correct	87 ms	5160 KB	Output is correct
15	Incorrect	192 ms	12364 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

답안 #133261

Compilation message