oj.uz

Submission #133264

# Submission time Handle Problem Language Result Execution time Memory
133264 2019-07-20T10:18:17 Z ekrem Minerals (JOI19_minerals) C++17
40 / 100
 225 ms 12528 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 = 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -