#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
//#define LOCAL
#ifndef LOCAL
#include "minerals.h"
#endif
#ifdef LOCAL
int32_t* arr;
std::map<int32_t, int32_t> kinds_cur;
int32_t ans_cur;
bool* taken_cur;
int32_t query_cnt = 0;
int32_t Query(int32_t ind) {
ind--;
query_cnt++;
if(taken_cur[ind]) {
kinds_cur[arr[ind]]--;
if(kinds_cur[arr[ind]] == 0)
ans_cur--;
} else {
kinds_cur[arr[ind]]++;
if(kinds_cur[arr[ind]] == 1)
ans_cur++;
}
taken_cur[ind] = !taken_cur[ind];
return ans_cur;
}
std::vector<std::pair<int32_t, int32_t> > ans_vec;
void Answer(int32_t a, int32_t b) {
a--;
b--;
ans_vec.emplace_back(a, b);
}
#endif
int32_t* perm;
bool* taken_cur2;
int32_t last_q;
int32_t query(int32_t ind) {
taken_cur2[ind] = !taken_cur2[ind];
last_q = Query(perm[ind] + 1);
return last_q;
}
void answer(int32_t a, int32_t b) {
Answer(perm[a] + 1, perm[b] + 1);
}
void rec_solve(std::vector<int32_t>& lefts, std::vector<int32_t>& rights) {
if(lefts.size() == 1) {
answer(lefts[0], rights[0]);
return;
}
int32_t cnt_left = 0;
int32_t cnt_right = 0;
for(int32_t i = 0; i < lefts.size(); i++) {
if(taken_cur2[lefts[i]])
cnt_left++;
if(taken_cur2[rights[i]])
cnt_right++;
}
int32_t steps_left = std::min(std::abs((int32_t)lefts.size() / 2 - cnt_left), std::abs((int32_t)(lefts.size() + 1) / 2 - cnt_left));
int32_t steps_right = std::min(std::abs((int32_t)rights.size() / 2 - cnt_right), std::abs((int32_t)(rights.size() + 1) / 2 - cnt_right));
if(steps_left > steps_right)
std::swap(lefts, rights);
std::vector<int32_t> lefts1, lefts2;
for(int32_t i = 0; i < lefts.size(); i++)
if(taken_cur2[lefts[i]])
lefts1.push_back(lefts[i]);
else
lefts2.push_back(lefts[i]);
while((int32_t)lefts1.size() - (int32_t)lefts2.size() > 1) {
query(lefts1.back());
lefts2.push_back(lefts1.back());
lefts1.pop_back();
}
while((int32_t)lefts2.size() - (int32_t)lefts1.size() > 1) {
query(lefts2.back());
lefts1.push_back(lefts2.back());
lefts2.pop_back();
}
std::sort(lefts1.begin(), lefts1.end());
std::sort(lefts2.begin(), lefts2.end());
std::vector<int32_t> rights1, rights2;
int32_t last = last_q;
for(int32_t i = 0; i < rights.size(); i++) {
int32_t new_ = query(rights[i]);
if(new_ != last)
rights2.push_back(rights[i]);
else
rights1.push_back(rights[i]);
last = new_;
if(rights1.size() == lefts1.size()) {
for(int32_t j = i + 1; j < rights.size(); j++)
rights2.push_back(rights[j]);
break;
}
if(rights2.size() == lefts2.size()) {
for(int32_t j = i + 1; j < rights.size(); j++)
rights1.push_back(rights[j]);
break;
}
}
rec_solve(lefts1, rights1);
rec_solve(lefts2, rights2);
}
void Solve(int32_t n) {
std::mt19937 rng2(12345);
perm = new int32_t[2 * n];
for(int32_t i = 0; i < 2 * n; i++)
perm[i] = i;
taken_cur2 = new bool[2 * n];
for (int32_t i = 0; i < 2 * n; i++)
taken_cur2[i] = false;
std::shuffle(perm, perm + 2 * n, rng2);
std::vector<int32_t> lefts, rights;
int32_t last = 0;
for(int32_t i = 0; i < 2 * n; i++) {
int32_t new_ = query(i);
if(new_ != last)
lefts.push_back(i);
else
rights.push_back(i);
last = new_;
}
rec_solve(lefts, rights);
}
#ifdef LOCAL
int main() {
int32_t n;
std::cin >> n;
std::mt19937 rng;
for(int32_t t = 0; t < 10; t++) {
arr = new int32_t[2 * n];
for (int32_t i = 0; i < 2 * n; i++)
arr[i] = i / 2;
std::shuffle(arr, arr + 2 * n, rng);
taken_cur = new bool[2 * n];
for (int32_t i = 0; i < 2 * n; i++)
taken_cur[i] = false;
ans_vec.clear();
kinds_cur.clear();
query_cnt = 0;
Solve(n);
if (ans_vec.size() != n) {
std::cout << "BAD";
return 0;
}
for (auto p: ans_vec)
if (arr[p.first] != arr[p.second]) {
std::cout << "BAD" << "\n";
return 0;
}
std::cout << "GOOD, used " << query_cnt << " queries" << "\n";
}
return 0;
}
#endif
Compilation message
minerals.cpp: In function 'void rec_solve(std::vector<int>&, std::vector<int>&)':
minerals.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int32_t i = 0; i < lefts.size(); i++) {
| ~~^~~~~~~~~~~~~~
minerals.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int32_t i = 0; i < lefts.size(); i++)
| ~~^~~~~~~~~~~~~~
minerals.cpp:113:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int32_t i = 0; i < rights.size(); i++) {
| ~~^~~~~~~~~~~~~~~
minerals.cpp:122:38: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int32_t j = i + 1; j < rights.size(); j++)
| ~~^~~~~~~~~~~~~~~
minerals.cpp:127:38: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for(int32_t j = i + 1; j < rights.size(); j++)
| ~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
2 ms |
336 KB |
Output is correct |
3 |
Correct |
5 ms |
464 KB |
Output is correct |
4 |
Correct |
9 ms |
720 KB |
Output is correct |
5 |
Correct |
20 ms |
1188 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
2 ms |
336 KB |
Output is correct |
7 |
Correct |
5 ms |
464 KB |
Output is correct |
8 |
Correct |
9 ms |
720 KB |
Output is correct |
9 |
Correct |
20 ms |
1188 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
13 ms |
976 KB |
Output is correct |
12 |
Correct |
18 ms |
1368 KB |
Output is correct |
13 |
Correct |
20 ms |
1360 KB |
Output is correct |
14 |
Correct |
23 ms |
1232 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
2 ms |
336 KB |
Output is correct |
7 |
Correct |
5 ms |
464 KB |
Output is correct |
8 |
Correct |
9 ms |
720 KB |
Output is correct |
9 |
Correct |
20 ms |
1188 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
13 ms |
976 KB |
Output is correct |
12 |
Correct |
18 ms |
1368 KB |
Output is correct |
13 |
Correct |
20 ms |
1360 KB |
Output is correct |
14 |
Correct |
23 ms |
1232 KB |
Output is correct |
15 |
Correct |
55 ms |
3008 KB |
Output is correct |
16 |
Correct |
53 ms |
3020 KB |
Output is correct |
17 |
Correct |
56 ms |
3020 KB |
Output is correct |
18 |
Correct |
56 ms |
2860 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
2 ms |
336 KB |
Output is correct |
7 |
Correct |
5 ms |
464 KB |
Output is correct |
8 |
Correct |
9 ms |
720 KB |
Output is correct |
9 |
Correct |
20 ms |
1188 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
13 ms |
976 KB |
Output is correct |
12 |
Correct |
18 ms |
1368 KB |
Output is correct |
13 |
Correct |
20 ms |
1360 KB |
Output is correct |
14 |
Correct |
23 ms |
1232 KB |
Output is correct |
15 |
Correct |
55 ms |
3008 KB |
Output is correct |
16 |
Correct |
53 ms |
3020 KB |
Output is correct |
17 |
Correct |
56 ms |
3020 KB |
Output is correct |
18 |
Correct |
56 ms |
2860 KB |
Output is correct |
19 |
Correct |
59 ms |
3144 KB |
Output is correct |
20 |
Correct |
55 ms |
3164 KB |
Output is correct |
21 |
Correct |
54 ms |
3176 KB |
Output is correct |
22 |
Correct |
56 ms |
3088 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
2 ms |
336 KB |
Output is correct |
7 |
Correct |
5 ms |
464 KB |
Output is correct |
8 |
Correct |
9 ms |
720 KB |
Output is correct |
9 |
Correct |
20 ms |
1188 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
13 ms |
976 KB |
Output is correct |
12 |
Correct |
18 ms |
1368 KB |
Output is correct |
13 |
Correct |
20 ms |
1360 KB |
Output is correct |
14 |
Correct |
23 ms |
1232 KB |
Output is correct |
15 |
Correct |
55 ms |
3008 KB |
Output is correct |
16 |
Correct |
53 ms |
3020 KB |
Output is correct |
17 |
Correct |
56 ms |
3020 KB |
Output is correct |
18 |
Correct |
56 ms |
2860 KB |
Output is correct |
19 |
Correct |
59 ms |
3144 KB |
Output is correct |
20 |
Correct |
55 ms |
3164 KB |
Output is correct |
21 |
Correct |
54 ms |
3176 KB |
Output is correct |
22 |
Correct |
56 ms |
3088 KB |
Output is correct |
23 |
Correct |
61 ms |
3228 KB |
Output is correct |
24 |
Correct |
61 ms |
3316 KB |
Output is correct |
25 |
Correct |
54 ms |
3268 KB |
Output is correct |
26 |
Correct |
56 ms |
3052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
2 ms |
336 KB |
Output is correct |
7 |
Correct |
5 ms |
464 KB |
Output is correct |
8 |
Correct |
9 ms |
720 KB |
Output is correct |
9 |
Correct |
20 ms |
1188 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
13 ms |
976 KB |
Output is correct |
12 |
Correct |
18 ms |
1368 KB |
Output is correct |
13 |
Correct |
20 ms |
1360 KB |
Output is correct |
14 |
Correct |
23 ms |
1232 KB |
Output is correct |
15 |
Correct |
55 ms |
3008 KB |
Output is correct |
16 |
Correct |
53 ms |
3020 KB |
Output is correct |
17 |
Correct |
56 ms |
3020 KB |
Output is correct |
18 |
Correct |
56 ms |
2860 KB |
Output is correct |
19 |
Correct |
59 ms |
3144 KB |
Output is correct |
20 |
Correct |
55 ms |
3164 KB |
Output is correct |
21 |
Correct |
54 ms |
3176 KB |
Output is correct |
22 |
Correct |
56 ms |
3088 KB |
Output is correct |
23 |
Correct |
61 ms |
3228 KB |
Output is correct |
24 |
Correct |
61 ms |
3316 KB |
Output is correct |
25 |
Correct |
54 ms |
3268 KB |
Output is correct |
26 |
Correct |
56 ms |
3052 KB |
Output is correct |
27 |
Correct |
57 ms |
3180 KB |
Output is correct |
28 |
Correct |
58 ms |
3284 KB |
Output is correct |
29 |
Correct |
57 ms |
3292 KB |
Output is correct |
30 |
Correct |
63 ms |
3144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
2 ms |
336 KB |
Output is correct |
7 |
Correct |
5 ms |
464 KB |
Output is correct |
8 |
Correct |
9 ms |
720 KB |
Output is correct |
9 |
Correct |
20 ms |
1188 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
13 ms |
976 KB |
Output is correct |
12 |
Correct |
18 ms |
1368 KB |
Output is correct |
13 |
Correct |
20 ms |
1360 KB |
Output is correct |
14 |
Correct |
23 ms |
1232 KB |
Output is correct |
15 |
Correct |
55 ms |
3008 KB |
Output is correct |
16 |
Correct |
53 ms |
3020 KB |
Output is correct |
17 |
Correct |
56 ms |
3020 KB |
Output is correct |
18 |
Correct |
56 ms |
2860 KB |
Output is correct |
19 |
Correct |
59 ms |
3144 KB |
Output is correct |
20 |
Correct |
55 ms |
3164 KB |
Output is correct |
21 |
Correct |
54 ms |
3176 KB |
Output is correct |
22 |
Correct |
56 ms |
3088 KB |
Output is correct |
23 |
Correct |
61 ms |
3228 KB |
Output is correct |
24 |
Correct |
61 ms |
3316 KB |
Output is correct |
25 |
Correct |
54 ms |
3268 KB |
Output is correct |
26 |
Correct |
56 ms |
3052 KB |
Output is correct |
27 |
Correct |
57 ms |
3180 KB |
Output is correct |
28 |
Correct |
58 ms |
3284 KB |
Output is correct |
29 |
Correct |
57 ms |
3292 KB |
Output is correct |
30 |
Correct |
63 ms |
3144 KB |
Output is correct |
31 |
Correct |
64 ms |
3332 KB |
Output is correct |
32 |
Correct |
59 ms |
3328 KB |
Output is correct |
33 |
Correct |
62 ms |
3360 KB |
Output is correct |
34 |
Correct |
70 ms |
3220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
2 ms |
336 KB |
Output is correct |
7 |
Correct |
5 ms |
464 KB |
Output is correct |
8 |
Correct |
9 ms |
720 KB |
Output is correct |
9 |
Correct |
20 ms |
1188 KB |
Output is correct |
10 |
Correct |
2 ms |
336 KB |
Output is correct |
11 |
Correct |
13 ms |
976 KB |
Output is correct |
12 |
Correct |
18 ms |
1368 KB |
Output is correct |
13 |
Correct |
20 ms |
1360 KB |
Output is correct |
14 |
Correct |
23 ms |
1232 KB |
Output is correct |
15 |
Correct |
55 ms |
3008 KB |
Output is correct |
16 |
Correct |
53 ms |
3020 KB |
Output is correct |
17 |
Correct |
56 ms |
3020 KB |
Output is correct |
18 |
Correct |
56 ms |
2860 KB |
Output is correct |
19 |
Correct |
59 ms |
3144 KB |
Output is correct |
20 |
Correct |
55 ms |
3164 KB |
Output is correct |
21 |
Correct |
54 ms |
3176 KB |
Output is correct |
22 |
Correct |
56 ms |
3088 KB |
Output is correct |
23 |
Correct |
61 ms |
3228 KB |
Output is correct |
24 |
Correct |
61 ms |
3316 KB |
Output is correct |
25 |
Correct |
54 ms |
3268 KB |
Output is correct |
26 |
Correct |
56 ms |
3052 KB |
Output is correct |
27 |
Correct |
57 ms |
3180 KB |
Output is correct |
28 |
Correct |
58 ms |
3284 KB |
Output is correct |
29 |
Correct |
57 ms |
3292 KB |
Output is correct |
30 |
Correct |
63 ms |
3144 KB |
Output is correct |
31 |
Correct |
64 ms |
3332 KB |
Output is correct |
32 |
Correct |
59 ms |
3328 KB |
Output is correct |
33 |
Correct |
62 ms |
3360 KB |
Output is correct |
34 |
Correct |
70 ms |
3220 KB |
Output is correct |
35 |
Correct |
63 ms |
3316 KB |
Output is correct |
36 |
Correct |
64 ms |
3384 KB |
Output is correct |
37 |
Correct |
63 ms |
3420 KB |
Output is correct |
38 |
Correct |
61 ms |
3148 KB |
Output is correct |