답안 #133264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133264	2019-07-20T10:18:17 Z	ekrem	Minerals (JOI19_minerals)	C++17	40 / 100	225 ms	12528 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, 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.0 / 6.0

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

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	632 KB	Output is correct
2	Correct	12 ms	1016 KB	Output is correct
3	Correct	25 ms	1528 KB	Output is correct
4	Correct	54 ms	2936 KB	Output is correct
5	Correct	114 ms	5092 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	296 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	248 KB	Output is correct
5	Correct	6 ms	632 KB	Output is correct
6	Correct	12 ms	1016 KB	Output is correct
7	Correct	25 ms	1528 KB	Output is correct
8	Correct	54 ms	2936 KB	Output is correct
9	Correct	114 ms	5092 KB	Output is correct
10	Correct	7 ms	632 KB	Output is correct
11	Correct	73 ms	3492 KB	Output is correct
12	Correct	119 ms	5152 KB	Output is correct
13	Correct	114 ms	5148 KB	Output is correct
14	Correct	115 ms	5096 KB	Output is correct

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	296 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	248 KB	Output is correct
5	Correct	6 ms	632 KB	Output is correct
6	Correct	12 ms	1016 KB	Output is correct
7	Correct	25 ms	1528 KB	Output is correct
8	Correct	54 ms	2936 KB	Output is correct
9	Correct	114 ms	5092 KB	Output is correct
10	Correct	7 ms	632 KB	Output is correct
11	Correct	73 ms	3492 KB	Output is correct
12	Correct	119 ms	5152 KB	Output is correct
13	Correct	114 ms	5148 KB	Output is correct
14	Correct	115 ms	5096 KB	Output is correct
15	Incorrect	225 ms	12528 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	296 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	248 KB	Output is correct
5	Correct	6 ms	632 KB	Output is correct
6	Correct	12 ms	1016 KB	Output is correct
7	Correct	25 ms	1528 KB	Output is correct
8	Correct	54 ms	2936 KB	Output is correct
9	Correct	114 ms	5092 KB	Output is correct
10	Correct	7 ms	632 KB	Output is correct
11	Correct	73 ms	3492 KB	Output is correct
12	Correct	119 ms	5152 KB	Output is correct
13	Correct	114 ms	5148 KB	Output is correct
14	Correct	115 ms	5096 KB	Output is correct
15	Incorrect	225 ms	12528 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	296 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	248 KB	Output is correct
5	Correct	6 ms	632 KB	Output is correct
6	Correct	12 ms	1016 KB	Output is correct
7	Correct	25 ms	1528 KB	Output is correct
8	Correct	54 ms	2936 KB	Output is correct
9	Correct	114 ms	5092 KB	Output is correct
10	Correct	7 ms	632 KB	Output is correct
11	Correct	73 ms	3492 KB	Output is correct
12	Correct	119 ms	5152 KB	Output is correct
13	Correct	114 ms	5148 KB	Output is correct
14	Correct	115 ms	5096 KB	Output is correct
15	Incorrect	225 ms	12528 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	296 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	248 KB	Output is correct
5	Correct	6 ms	632 KB	Output is correct
6	Correct	12 ms	1016 KB	Output is correct
7	Correct	25 ms	1528 KB	Output is correct
8	Correct	54 ms	2936 KB	Output is correct
9	Correct	114 ms	5092 KB	Output is correct
10	Correct	7 ms	632 KB	Output is correct
11	Correct	73 ms	3492 KB	Output is correct
12	Correct	119 ms	5152 KB	Output is correct
13	Correct	114 ms	5148 KB	Output is correct
14	Correct	115 ms	5096 KB	Output is correct
15	Incorrect	225 ms	12528 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	296 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	248 KB	Output is correct
5	Correct	6 ms	632 KB	Output is correct
6	Correct	12 ms	1016 KB	Output is correct
7	Correct	25 ms	1528 KB	Output is correct
8	Correct	54 ms	2936 KB	Output is correct
9	Correct	114 ms	5092 KB	Output is correct
10	Correct	7 ms	632 KB	Output is correct
11	Correct	73 ms	3492 KB	Output is correct
12	Correct	119 ms	5152 KB	Output is correct
13	Correct	114 ms	5148 KB	Output is correct
14	Correct	115 ms	5096 KB	Output is correct
15	Incorrect	225 ms	12528 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	296 KB	Output is correct
3	Correct	2 ms	248 KB	Output is correct
4	Correct	2 ms	248 KB	Output is correct
5	Correct	6 ms	632 KB	Output is correct
6	Correct	12 ms	1016 KB	Output is correct
7	Correct	25 ms	1528 KB	Output is correct
8	Correct	54 ms	2936 KB	Output is correct
9	Correct	114 ms	5092 KB	Output is correct
10	Correct	7 ms	632 KB	Output is correct
11	Correct	73 ms	3492 KB	Output is correct
12	Correct	119 ms	5152 KB	Output is correct
13	Correct	114 ms	5148 KB	Output is correct
14	Correct	115 ms	5096 KB	Output is correct
15	Incorrect	225 ms	12528 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

답안 #133264

Compilation message