oj.uz

Submission #133901

# Submission time Handle Problem Language Result Execution time Memory
133901 2019-07-21T17:03:17 Z ekrem Minerals (JOI19_minerals) C++17
40 / 100
 249 ms 12792 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){
	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);
	coz(a, y);
	coz(x, b);
}

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);
	// 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 376 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 252 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 1528 KB Output is correct
4 Correct 46 ms 2808 KB Output is correct
5 Correct 100 ms 5208 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 252 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 1528 KB Output is correct
8 Correct 46 ms 2808 KB Output is correct
9 Correct 100 ms 5208 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 60 ms 3704 KB Output is correct
12 Correct 98 ms 5288 KB Output is correct
13 Correct 98 ms 5372 KB Output is correct
14 Correct 95 ms 5112 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 252 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 1528 KB Output is correct
8 Correct 46 ms 2808 KB Output is correct
9 Correct 100 ms 5208 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 60 ms 3704 KB Output is correct
12 Correct 98 ms 5288 KB Output is correct
13 Correct 98 ms 5372 KB Output is correct
14 Correct 95 ms 5112 KB Output is correct
15 Incorrect 249 ms 12792 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 252 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 1528 KB Output is correct
8 Correct 46 ms 2808 KB Output is correct
9 Correct 100 ms 5208 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 60 ms 3704 KB Output is correct
12 Correct 98 ms 5288 KB Output is correct
13 Correct 98 ms 5372 KB Output is correct
14 Correct 95 ms 5112 KB Output is correct
15 Incorrect 249 ms 12792 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 252 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 1528 KB Output is correct
8 Correct 46 ms 2808 KB Output is correct
9 Correct 100 ms 5208 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 60 ms 3704 KB Output is correct
12 Correct 98 ms 5288 KB Output is correct
13 Correct 98 ms 5372 KB Output is correct
14 Correct 95 ms 5112 KB Output is correct
15 Incorrect 249 ms 12792 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 252 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 1528 KB Output is correct
8 Correct 46 ms 2808 KB Output is correct
9 Correct 100 ms 5208 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 60 ms 3704 KB Output is correct
12 Correct 98 ms 5288 KB Output is correct
13 Correct 98 ms 5372 KB Output is correct
14 Correct 95 ms 5112 KB Output is correct
15 Incorrect 249 ms 12792 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 252 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 1528 KB Output is correct
8 Correct 46 ms 2808 KB Output is correct
9 Correct 100 ms 5208 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 60 ms 3704 KB Output is correct
12 Correct 98 ms 5288 KB Output is correct
13 Correct 98 ms 5372 KB Output is correct
14 Correct 95 ms 5112 KB Output is correct
15 Incorrect 249 ms 12792 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 252 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 1528 KB Output is correct
8 Correct 46 ms 2808 KB Output is correct
9 Correct 100 ms 5208 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 60 ms 3704 KB Output is correct
12 Correct 98 ms 5288 KB Output is correct
13 Correct 98 ms 5372 KB Output is correct
14 Correct 95 ms 5112 KB Output is correct
15 Incorrect 249 ms 12792 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -