oj.uz

Submission #133903

# Submission time Handle Problem Language Result Execution time Memory
133903 2019-07-21T17:16:31 Z ekrem Minerals (JOI19_minerals) C++17
80 / 100
 315 ms 13892 KB 

#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, onc, h[MAXN], aa[MAXN];
set < int > :: iterator it;

int myrandom(int x){
	return rand()%x;
}

int sor(int x){
	if(h[x])
		top--;
	else
		top++;
	h[x] = 1 - h[x];
	return top - Query(aa[x]);
}

void coz(si a, si b, int d){
	if(a.size() == 1){
		Answer(aa[*a.begin()], aa[*b.begin()]);
		return;
	}
	int n = a.size();
	si x, y;
	for(int i = 1; i <= n/2; i++){
		int of = *a.begin();
		a.erase(of);
		x.insert(of);
		onc = sor(of);
	}
	for(it = b.begin(); it != b.end(); it++){
		int don = sor(*it);
		if(don != onc){
			y.insert(*it);
		}
		onc = don;
	}
	for(it = y.begin(); it != y.end(); it++)
		b.erase(*it);
	// for(it = x.begin(); it != x.end(); it++)
	// 	onc = sor(*it);
	if(d == 1){
		coz(a, y, 1);
		coz(x, b, 0);
	} else{
		coz(x, y, 1);
		coz(a, b, 0);
	}
}

void Solve(int N) {
	n = N+N;
	srand(time(0));
	for(int i = 1; i <= n; i++)
		aa[i] = i;
	random_shuffle(aa + 1, aa + n + 1, myrandom);
	// for(int i = 1; i <= n; i++)
	// 	cout << aa[i] << " ";cout << endl;
	set < int > a, b;
	for(int i = 1; i <= n; i++){
		int don = sor(i);
		// cout << don << " " << onc << endl;
		if(don > onc)
			a.insert(i);
		else
			b.insert(i);
		onc = don;
	}
	coz(a, b, 1);
	// for(it = a.begin(); it != a.end(); it++)cout << *it << " ";cout << endl;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 276 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 10 ms 888 KB Output is correct
3 Correct 21 ms 1656 KB Output is correct
4 Correct 45 ms 2808 KB Output is correct
5 Correct 94 ms 5112 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 276 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 10 ms 888 KB Output is correct
7 Correct 21 ms 1656 KB Output is correct
8 Correct 45 ms 2808 KB Output is correct
9 Correct 94 ms 5112 KB Output is correct
10 Correct 6 ms 636 KB Output is correct
11 Correct 58 ms 3576 KB Output is correct
12 Correct 93 ms 5272 KB Output is correct
13 Correct 96 ms 5368 KB Output is correct
14 Correct 94 ms 5204 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 276 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 10 ms 888 KB Output is correct
7 Correct 21 ms 1656 KB Output is correct
8 Correct 45 ms 2808 KB Output is correct
9 Correct 94 ms 5112 KB Output is correct
10 Correct 6 ms 636 KB Output is correct
11 Correct 58 ms 3576 KB Output is correct
12 Correct 93 ms 5272 KB Output is correct
13 Correct 96 ms 5368 KB Output is correct
14 Correct 94 ms 5204 KB Output is correct
15 Correct 286 ms 12828 KB Output is correct
16 Correct 283 ms 12824 KB Output is correct
17 Correct 292 ms 12868 KB Output is correct
18 Correct 286 ms 12832 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 276 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 10 ms 888 KB Output is correct
7 Correct 21 ms 1656 KB Output is correct
8 Correct 45 ms 2808 KB Output is correct
9 Correct 94 ms 5112 KB Output is correct
10 Correct 6 ms 636 KB Output is correct
11 Correct 58 ms 3576 KB Output is correct
12 Correct 93 ms 5272 KB Output is correct
13 Correct 96 ms 5368 KB Output is correct
14 Correct 94 ms 5204 KB Output is correct
15 Correct 286 ms 12828 KB Output is correct
16 Correct 283 ms 12824 KB Output is correct
17 Correct 292 ms 12868 KB Output is correct
18 Correct 286 ms 12832 KB Output is correct
19 Correct 315 ms 13176 KB Output is correct
20 Correct 290 ms 13224 KB Output is correct
21 Correct 298 ms 13048 KB Output is correct
22 Correct 302 ms 12924 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 276 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 10 ms 888 KB Output is correct
7 Correct 21 ms 1656 KB Output is correct
8 Correct 45 ms 2808 KB Output is correct
9 Correct 94 ms 5112 KB Output is correct
10 Correct 6 ms 636 KB Output is correct
11 Correct 58 ms 3576 KB Output is correct
12 Correct 93 ms 5272 KB Output is correct
13 Correct 96 ms 5368 KB Output is correct
14 Correct 94 ms 5204 KB Output is correct
15 Correct 286 ms 12828 KB Output is correct
16 Correct 283 ms 12824 KB Output is correct
17 Correct 292 ms 12868 KB Output is correct
18 Correct 286 ms 12832 KB Output is correct
19 Correct 315 ms 13176 KB Output is correct
20 Correct 290 ms 13224 KB Output is correct
21 Correct 298 ms 13048 KB Output is correct
22 Correct 302 ms 12924 KB Output is correct
23 Correct 296 ms 13492 KB Output is correct
24 Correct 295 ms 13560 KB Output is correct
25 Correct 296 ms 13492 KB Output is correct
26 Correct 302 ms 13328 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 276 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 10 ms 888 KB Output is correct
7 Correct 21 ms 1656 KB Output is correct
8 Correct 45 ms 2808 KB Output is correct
9 Correct 94 ms 5112 KB Output is correct
10 Correct 6 ms 636 KB Output is correct
11 Correct 58 ms 3576 KB Output is correct
12 Correct 93 ms 5272 KB Output is correct
13 Correct 96 ms 5368 KB Output is correct
14 Correct 94 ms 5204 KB Output is correct
15 Correct 286 ms 12828 KB Output is correct
16 Correct 283 ms 12824 KB Output is correct
17 Correct 292 ms 12868 KB Output is correct
18 Correct 286 ms 12832 KB Output is correct
19 Correct 315 ms 13176 KB Output is correct
20 Correct 290 ms 13224 KB Output is correct
21 Correct 298 ms 13048 KB Output is correct
22 Correct 302 ms 12924 KB Output is correct
23 Correct 296 ms 13492 KB Output is correct
24 Correct 295 ms 13560 KB Output is correct
25 Correct 296 ms 13492 KB Output is correct
26 Correct 302 ms 13328 KB Output is correct
27 Incorrect 298 ms 13892 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 276 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 10 ms 888 KB Output is correct
7 Correct 21 ms 1656 KB Output is correct
8 Correct 45 ms 2808 KB Output is correct
9 Correct 94 ms 5112 KB Output is correct
10 Correct 6 ms 636 KB Output is correct
11 Correct 58 ms 3576 KB Output is correct
12 Correct 93 ms 5272 KB Output is correct
13 Correct 96 ms 5368 KB Output is correct
14 Correct 94 ms 5204 KB Output is correct
15 Correct 286 ms 12828 KB Output is correct
16 Correct 283 ms 12824 KB Output is correct
17 Correct 292 ms 12868 KB Output is correct
18 Correct 286 ms 12832 KB Output is correct
19 Correct 315 ms 13176 KB Output is correct
20 Correct 290 ms 13224 KB Output is correct
21 Correct 298 ms 13048 KB Output is correct
22 Correct 302 ms 12924 KB Output is correct
23 Correct 296 ms 13492 KB Output is correct
24 Correct 295 ms 13560 KB Output is correct
25 Correct 296 ms 13492 KB Output is correct
26 Correct 302 ms 13328 KB Output is correct
27 Incorrect 298 ms 13892 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 276 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 10 ms 888 KB Output is correct
7 Correct 21 ms 1656 KB Output is correct
8 Correct 45 ms 2808 KB Output is correct
9 Correct 94 ms 5112 KB Output is correct
10 Correct 6 ms 636 KB Output is correct
11 Correct 58 ms 3576 KB Output is correct
12 Correct 93 ms 5272 KB Output is correct
13 Correct 96 ms 5368 KB Output is correct
14 Correct 94 ms 5204 KB Output is correct
15 Correct 286 ms 12828 KB Output is correct
16 Correct 283 ms 12824 KB Output is correct
17 Correct 292 ms 12868 KB Output is correct
18 Correct 286 ms 12832 KB Output is correct
19 Correct 315 ms 13176 KB Output is correct
20 Correct 290 ms 13224 KB Output is correct
21 Correct 298 ms 13048 KB Output is correct
22 Correct 302 ms 12924 KB Output is correct
23 Correct 296 ms 13492 KB Output is correct
24 Correct 295 ms 13560 KB Output is correct
25 Correct 296 ms 13492 KB Output is correct
26 Correct 302 ms 13328 KB Output is correct
27 Incorrect 298 ms 13892 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -