oj.uz

Submission #133261

# Submission time Handle Problem Language Result Execution time Memory
133261 2019-07-20T10:12:59 Z ekrem Minerals (JOI19_minerals) C++17
40 / 100
 192 ms 12364 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, 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

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

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

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

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

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

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

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

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

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