#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 43000;
int perm[2 * MAX_N + 1];
bool inSet[2 * MAX_N + 1];
vector<int> firstt, secondd;
int ans = 0;
auto seed = default_random_engine( 69696 );
void solve( vector <int> &f, vector<int> &s ) {
if ( f.size() == 1 && s.size() == 1 ) {
Answer( s[0], f[0] );
return;
}
vector<int> fl, fr, sl, sr;
bool status = inSet[f[0]] ^ 1;
int mid = (f.size() < 10 ? f.size() / 2 : min( (int)f.size() - 1, ((int)(f.size() * 0.369))) );
int leftt = 0, rightt = 0;
for ( int i = 0; i < mid; i++ ) {
if ( inSet[f[i]] != status ) {
ans = Query( f[i] );
inSet[f[i]] = status;
}
fl.push_back( f[i] );
leftt++;
}
for ( int i = mid; i < f.size(); i++ ) {
if ( inSet[f[i]] == status ) {
ans = Query( f[i] );
inSet[f[i]] = status ^ 1;
}
fr.push_back( f[i] );
rightt++;
}
shuffle( s.begin(), s.end(), seed );
for ( int i = 0; i < s.size(); i++ ) {
if ( rightt == 0 ) {
sl.push_back( s[i] );
leftt--;
continue;
}
if ( leftt == 0 ) {
sr.push_back( s[i] );
rightt--;
continue;
}
int prevAns = ans;
ans = Query( s[i] );
inSet[s[i]] ^= 1;
if ( (status == true && ans == prevAns) || (status == false && ans != prevAns) ) {
sl.push_back( s[i] );
leftt--;
} else {
sr.push_back( s[i] );
rightt--;
}
}
solve( fl, sl );
solve( fr, sr );
}
void Solve( int n ) {
for ( int i = 1; i <= 2 * n; i++ )
perm[i] = i;
shuffle( perm + 1, perm + 1 + 2 * n, seed );
int prevAns = 0;
for ( int i = 1; i <= 2 * n; i++ ) {
if ( firstt.size() == n ) {
secondd.push_back( perm[i] );
continue;
}
ans = Query( perm[i] );
inSet[perm[i]] = true;
if ( ans > prevAns )
firstt.push_back( perm[i] );
else
secondd.push_back( perm[i] );
prevAns = ans;
}
shuffle( firstt.begin(), firstt.end(), seed );
shuffle( secondd.begin(), secondd.end(), seed );
solve( firstt, secondd );
}
Compilation message
minerals.cpp: In function 'void solve(std::vector<int>&, std::vector<int>&)':
minerals.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for ( int i = mid; i < f.size(); i++ ) {
| ~~^~~~~~~~~~
minerals.cpp:44:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for ( int i = 0; i < s.size(); i++ ) {
| ~~^~~~~~~~~~
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:79:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
79 | if ( firstt.size() == n ) {
| ~~~~~~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
2 ms |
600 KB |
Output is correct |
3 |
Correct |
3 ms |
600 KB |
Output is correct |
4 |
Correct |
7 ms |
1112 KB |
Output is correct |
5 |
Correct |
13 ms |
1368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
3 ms |
600 KB |
Output is correct |
8 |
Correct |
7 ms |
1112 KB |
Output is correct |
9 |
Correct |
13 ms |
1368 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
9 ms |
1024 KB |
Output is correct |
12 |
Correct |
14 ms |
1580 KB |
Output is correct |
13 |
Correct |
15 ms |
1792 KB |
Output is correct |
14 |
Correct |
14 ms |
1624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
3 ms |
600 KB |
Output is correct |
8 |
Correct |
7 ms |
1112 KB |
Output is correct |
9 |
Correct |
13 ms |
1368 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
9 ms |
1024 KB |
Output is correct |
12 |
Correct |
14 ms |
1580 KB |
Output is correct |
13 |
Correct |
15 ms |
1792 KB |
Output is correct |
14 |
Correct |
14 ms |
1624 KB |
Output is correct |
15 |
Correct |
37 ms |
3288 KB |
Output is correct |
16 |
Correct |
37 ms |
3152 KB |
Output is correct |
17 |
Correct |
45 ms |
3288 KB |
Output is correct |
18 |
Correct |
36 ms |
3024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
3 ms |
600 KB |
Output is correct |
8 |
Correct |
7 ms |
1112 KB |
Output is correct |
9 |
Correct |
13 ms |
1368 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
9 ms |
1024 KB |
Output is correct |
12 |
Correct |
14 ms |
1580 KB |
Output is correct |
13 |
Correct |
15 ms |
1792 KB |
Output is correct |
14 |
Correct |
14 ms |
1624 KB |
Output is correct |
15 |
Correct |
37 ms |
3288 KB |
Output is correct |
16 |
Correct |
37 ms |
3152 KB |
Output is correct |
17 |
Correct |
45 ms |
3288 KB |
Output is correct |
18 |
Correct |
36 ms |
3024 KB |
Output is correct |
19 |
Correct |
41 ms |
3280 KB |
Output is correct |
20 |
Correct |
40 ms |
3288 KB |
Output is correct |
21 |
Correct |
43 ms |
3352 KB |
Output is correct |
22 |
Correct |
37 ms |
3388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
3 ms |
600 KB |
Output is correct |
8 |
Correct |
7 ms |
1112 KB |
Output is correct |
9 |
Correct |
13 ms |
1368 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
9 ms |
1024 KB |
Output is correct |
12 |
Correct |
14 ms |
1580 KB |
Output is correct |
13 |
Correct |
15 ms |
1792 KB |
Output is correct |
14 |
Correct |
14 ms |
1624 KB |
Output is correct |
15 |
Correct |
37 ms |
3288 KB |
Output is correct |
16 |
Correct |
37 ms |
3152 KB |
Output is correct |
17 |
Correct |
45 ms |
3288 KB |
Output is correct |
18 |
Correct |
36 ms |
3024 KB |
Output is correct |
19 |
Correct |
41 ms |
3280 KB |
Output is correct |
20 |
Correct |
40 ms |
3288 KB |
Output is correct |
21 |
Correct |
43 ms |
3352 KB |
Output is correct |
22 |
Correct |
37 ms |
3388 KB |
Output is correct |
23 |
Correct |
40 ms |
3284 KB |
Output is correct |
24 |
Correct |
45 ms |
3192 KB |
Output is correct |
25 |
Correct |
39 ms |
3408 KB |
Output is correct |
26 |
Correct |
40 ms |
3556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
3 ms |
600 KB |
Output is correct |
8 |
Correct |
7 ms |
1112 KB |
Output is correct |
9 |
Correct |
13 ms |
1368 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
9 ms |
1024 KB |
Output is correct |
12 |
Correct |
14 ms |
1580 KB |
Output is correct |
13 |
Correct |
15 ms |
1792 KB |
Output is correct |
14 |
Correct |
14 ms |
1624 KB |
Output is correct |
15 |
Correct |
37 ms |
3288 KB |
Output is correct |
16 |
Correct |
37 ms |
3152 KB |
Output is correct |
17 |
Correct |
45 ms |
3288 KB |
Output is correct |
18 |
Correct |
36 ms |
3024 KB |
Output is correct |
19 |
Correct |
41 ms |
3280 KB |
Output is correct |
20 |
Correct |
40 ms |
3288 KB |
Output is correct |
21 |
Correct |
43 ms |
3352 KB |
Output is correct |
22 |
Correct |
37 ms |
3388 KB |
Output is correct |
23 |
Correct |
40 ms |
3284 KB |
Output is correct |
24 |
Correct |
45 ms |
3192 KB |
Output is correct |
25 |
Correct |
39 ms |
3408 KB |
Output is correct |
26 |
Correct |
40 ms |
3556 KB |
Output is correct |
27 |
Correct |
41 ms |
3568 KB |
Output is correct |
28 |
Correct |
40 ms |
3412 KB |
Output is correct |
29 |
Correct |
45 ms |
3812 KB |
Output is correct |
30 |
Correct |
42 ms |
3552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
3 ms |
600 KB |
Output is correct |
8 |
Correct |
7 ms |
1112 KB |
Output is correct |
9 |
Correct |
13 ms |
1368 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
9 ms |
1024 KB |
Output is correct |
12 |
Correct |
14 ms |
1580 KB |
Output is correct |
13 |
Correct |
15 ms |
1792 KB |
Output is correct |
14 |
Correct |
14 ms |
1624 KB |
Output is correct |
15 |
Correct |
37 ms |
3288 KB |
Output is correct |
16 |
Correct |
37 ms |
3152 KB |
Output is correct |
17 |
Correct |
45 ms |
3288 KB |
Output is correct |
18 |
Correct |
36 ms |
3024 KB |
Output is correct |
19 |
Correct |
41 ms |
3280 KB |
Output is correct |
20 |
Correct |
40 ms |
3288 KB |
Output is correct |
21 |
Correct |
43 ms |
3352 KB |
Output is correct |
22 |
Correct |
37 ms |
3388 KB |
Output is correct |
23 |
Correct |
40 ms |
3284 KB |
Output is correct |
24 |
Correct |
45 ms |
3192 KB |
Output is correct |
25 |
Correct |
39 ms |
3408 KB |
Output is correct |
26 |
Correct |
40 ms |
3556 KB |
Output is correct |
27 |
Correct |
41 ms |
3568 KB |
Output is correct |
28 |
Correct |
40 ms |
3412 KB |
Output is correct |
29 |
Correct |
45 ms |
3812 KB |
Output is correct |
30 |
Correct |
42 ms |
3552 KB |
Output is correct |
31 |
Correct |
42 ms |
3564 KB |
Output is correct |
32 |
Correct |
42 ms |
3560 KB |
Output is correct |
33 |
Correct |
43 ms |
3652 KB |
Output is correct |
34 |
Correct |
41 ms |
3248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
2 ms |
600 KB |
Output is correct |
7 |
Correct |
3 ms |
600 KB |
Output is correct |
8 |
Correct |
7 ms |
1112 KB |
Output is correct |
9 |
Correct |
13 ms |
1368 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
9 ms |
1024 KB |
Output is correct |
12 |
Correct |
14 ms |
1580 KB |
Output is correct |
13 |
Correct |
15 ms |
1792 KB |
Output is correct |
14 |
Correct |
14 ms |
1624 KB |
Output is correct |
15 |
Correct |
37 ms |
3288 KB |
Output is correct |
16 |
Correct |
37 ms |
3152 KB |
Output is correct |
17 |
Correct |
45 ms |
3288 KB |
Output is correct |
18 |
Correct |
36 ms |
3024 KB |
Output is correct |
19 |
Correct |
41 ms |
3280 KB |
Output is correct |
20 |
Correct |
40 ms |
3288 KB |
Output is correct |
21 |
Correct |
43 ms |
3352 KB |
Output is correct |
22 |
Correct |
37 ms |
3388 KB |
Output is correct |
23 |
Correct |
40 ms |
3284 KB |
Output is correct |
24 |
Correct |
45 ms |
3192 KB |
Output is correct |
25 |
Correct |
39 ms |
3408 KB |
Output is correct |
26 |
Correct |
40 ms |
3556 KB |
Output is correct |
27 |
Correct |
41 ms |
3568 KB |
Output is correct |
28 |
Correct |
40 ms |
3412 KB |
Output is correct |
29 |
Correct |
45 ms |
3812 KB |
Output is correct |
30 |
Correct |
42 ms |
3552 KB |
Output is correct |
31 |
Correct |
42 ms |
3564 KB |
Output is correct |
32 |
Correct |
42 ms |
3560 KB |
Output is correct |
33 |
Correct |
43 ms |
3652 KB |
Output is correct |
34 |
Correct |
41 ms |
3248 KB |
Output is correct |
35 |
Correct |
43 ms |
3416 KB |
Output is correct |
36 |
Correct |
44 ms |
3400 KB |
Output is correct |
37 |
Correct |
42 ms |
3664 KB |
Output is correct |
38 |
Correct |
44 ms |
3640 KB |
Output is correct |