oj.uz

Submission #133267

# Submission time Handle Problem Language Result Execution time Memory
133267 2019-07-20T10:24:52 Z ekrem Minerals (JOI19_minerals) C++14
40 / 100
 227 ms 12580 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 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 3 ms 380 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 13 ms 888 KB Output is correct
3 Correct 27 ms 1656 KB Output is correct
4 Correct 55 ms 2948 KB Output is correct
5 Correct 114 ms 5112 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 248 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 13 ms 888 KB Output is correct
7 Correct 27 ms 1656 KB Output is correct
8 Correct 55 ms 2948 KB Output is correct
9 Correct 114 ms 5112 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 72 ms 3576 KB Output is correct
12 Correct 117 ms 5148 KB Output is correct
13 Correct 115 ms 5148 KB Output is correct
14 Correct 116 ms 5084 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 248 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 13 ms 888 KB Output is correct
7 Correct 27 ms 1656 KB Output is correct
8 Correct 55 ms 2948 KB Output is correct
9 Correct 114 ms 5112 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 72 ms 3576 KB Output is correct
12 Correct 117 ms 5148 KB Output is correct
13 Correct 115 ms 5148 KB Output is correct
14 Correct 116 ms 5084 KB Output is correct
15 Incorrect 227 ms 12580 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 248 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 13 ms 888 KB Output is correct
7 Correct 27 ms 1656 KB Output is correct
8 Correct 55 ms 2948 KB Output is correct
9 Correct 114 ms 5112 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 72 ms 3576 KB Output is correct
12 Correct 117 ms 5148 KB Output is correct
13 Correct 115 ms 5148 KB Output is correct
14 Correct 116 ms 5084 KB Output is correct
15 Incorrect 227 ms 12580 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 248 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 13 ms 888 KB Output is correct
7 Correct 27 ms 1656 KB Output is correct
8 Correct 55 ms 2948 KB Output is correct
9 Correct 114 ms 5112 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 72 ms 3576 KB Output is correct
12 Correct 117 ms 5148 KB Output is correct
13 Correct 115 ms 5148 KB Output is correct
14 Correct 116 ms 5084 KB Output is correct
15 Incorrect 227 ms 12580 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 248 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 13 ms 888 KB Output is correct
7 Correct 27 ms 1656 KB Output is correct
8 Correct 55 ms 2948 KB Output is correct
9 Correct 114 ms 5112 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 72 ms 3576 KB Output is correct
12 Correct 117 ms 5148 KB Output is correct
13 Correct 115 ms 5148 KB Output is correct
14 Correct 116 ms 5084 KB Output is correct
15 Incorrect 227 ms 12580 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 248 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 13 ms 888 KB Output is correct
7 Correct 27 ms 1656 KB Output is correct
8 Correct 55 ms 2948 KB Output is correct
9 Correct 114 ms 5112 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 72 ms 3576 KB Output is correct
12 Correct 117 ms 5148 KB Output is correct
13 Correct 115 ms 5148 KB Output is correct
14 Correct 116 ms 5084 KB Output is correct
15 Incorrect 227 ms 12580 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 248 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 6 ms 632 KB Output is correct
6 Correct 13 ms 888 KB Output is correct
7 Correct 27 ms 1656 KB Output is correct
8 Correct 55 ms 2948 KB Output is correct
9 Correct 114 ms 5112 KB Output is correct
10 Correct 6 ms 632 KB Output is correct
11 Correct 72 ms 3576 KB Output is correct
12 Correct 117 ms 5148 KB Output is correct
13 Correct 115 ms 5148 KB Output is correct
14 Correct 116 ms 5084 KB Output is correct
15 Incorrect 227 ms 12580 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -