#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) {
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) {
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]);
return last_q;
}
void answer(int32_t a, int32_t b) {
Answer(perm[a], perm[b]);
}
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:78: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]
78 | for(int32_t i = 0; i < lefts.size(); i++) {
| ~~^~~~~~~~~~~~~~
minerals.cpp:90: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]
90 | for(int32_t i = 0; i < lefts.size(); i++)
| ~~^~~~~~~~~~~~~~
minerals.cpp:110: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]
110 | for(int32_t i = 0; i < rights.size(); i++) {
| ~~^~~~~~~~~~~~~~~
minerals.cpp:119: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]
119 | for(int32_t j = i + 1; j < rights.size(); j++)
| ~~^~~~~~~~~~~~~~~
minerals.cpp:124: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]
124 | for(int32_t j = i + 1; j < rights.size(); j++)
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
208 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
