#include <bits/stdc++.h>
void Solve(int N);
int Query(int x);
void Answer(int x, int y);
bool inMachine[100005];
int lastRes = 0;
int opCount = 0;
void setInMachine(int i, bool val) {
if (inMachine[i] != val) {
lastRes = Query(i);
opCount++;
inMachine[i] = val;
}
}
void flip(int i) {
setInMachine(i, !inMachine[i]);
}
int query() {
return lastRes;
}
std::mt19937 rand(0);
void findMatching(std::vector<int>& a, std::vector<int>& b, bool aIsSet) {
if (a.size() == 0)
exit(1);
if (a.size() == 1) {
Answer(a[0], b[0]);
return;
}
std::shuffle(a.begin(), a.end(), rand);
std::shuffle(b.begin(), b.end(), rand);
std::vector<int> a1, a2, b1, b2;
int bound;
if (aIsSet) {
bound = (3 - sqrt(5)) / 2 * a.size();
} else {
bound = (1 - (3 - sqrt(5)) / 2) * a.size();
}
if (bound == 0) bound++;
if (bound == a.size()) bound--;
for (int i = 0; i < a.size(); i++) {
if (i < bound) {
a1.push_back(a[i]);
} else {
a2.push_back(a[i]);
}
}
//std::cout << a1.size() << " " << a2.size() << std::endl;
for (int x: a1) {
setInMachine(x, false);
}
for (int x: a2) {
setInMachine(x, true);
}
for (int x: b) {
if (a1.size() == b1.size()) b2.push_back(x);
else if (a2.size() == b2.size()) b1.push_back(x);
else {
int prev = query();
flip(x);
if (prev != query()) {
b1.push_back(x);
} else {
b2.push_back(x);
}
}
}
//std::cout << a1.size() << " " << b1.size() << std::endl;
findMatching(a1, b1, false);
findMatching(a2, b2, true);
}
void Solve(int N) {
lastRes = 0;
opCount = 0;
memset(inMachine, 0, sizeof(inMachine));
std::vector<int> a, b;
for (int i = 1; i <= 2 * N; i++) {
int prev = query();
flip(i);
if (prev == query()) {
b.push_back(i);
} else {
a.push_back(i);
}
}
findMatching(a, b, true);
}
#ifdef LOCAL_TEST
#include <cstdio>
#include <cstdlib>
#include <algorithm>
constexpr int MAX_N = 43000;
constexpr int MAX_CALLS = 1000000;
namespace {
void WrongAnswer(int code) {
printf("Wrong Answer [%d]\n", code);
exit(0);
}
int N;
int counterpart[2 * MAX_N + 1];
int num_queries;
int num_kinds;
int on[2 * MAX_N + 1];
int count[2 * MAX_N + 1];
int num_answers;
int answer[2 * MAX_N + 1];
} // namespace
int Query(int x) {
if (!(1 <= x && x <= 2 * N)) {
printf("Query(%d)\n", x);
WrongAnswer(1);
}
if (++num_queries > MAX_CALLS) {
//WrongAnswer(2);
}
const int type = std::min(x, counterpart[x]);
if (on[x]) {
--on[x];
--count[type];
if (count[type] == 0) {
--num_kinds;
}
} else {
++on[x];
++count[type];
if (count[type] == 1) {
++num_kinds;
}
}
return num_kinds;
}
void Answer(int a, int b) {
if (N < 100)
std::cout << "Answer(" << a << ", " << b << ")" << std::endl;
if (++num_answers > N) {
WrongAnswer(6);
}
if (!(1 <= a && a <= 2 * N && 1 <= b && b <= 2 * N)) {
WrongAnswer(3);
}
if (answer[a] != 0) {
WrongAnswer(4);
}
answer[a] = b;
if (answer[b] != 0) {
WrongAnswer(4);
}
answer[b] = a;
if (!(counterpart[a] == b && counterpart[b] == a)) {
WrongAnswer(5);
}
}
int secret_order[100000];
int main() {
if (scanf("%d", &N) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
for (int i = 0; i < 2 * N; ++i) {
secret_order[i] = i + 1;
}
std::random_device rd;
std::mt19937 rng(rd());
int maxQueries = 0;
for (int iter = 0; iter < 100; iter++) {
num_queries = 0;
num_kinds = 0;
memset(on, 0, sizeof(on));
memset(count, 0, sizeof(count));
num_answers = 0;
memset(answer, 0, sizeof(answer));
memset(counterpart, 0, sizeof(counterpart));
std::shuffle(secret_order, secret_order + 2 * N, rng);
for (int i = 1; i <= N; ++i) {
int x, y;
x = secret_order[2 * i - 2];
y = secret_order[2 * i - 1];
/*if (scanf("%d%d", &x, &y) != 2) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}*/
if (N < 100)
printf("%d %d\n", x, y);
counterpart[x] = y;
counterpart[y] = x;
}
Solve(N);
if (num_answers != N) {
WrongAnswer(6);
}
printf("Accepted: %d\n", num_queries);
maxQueries = std::max(maxQueries, num_queries);
}
std::cout << "Max queries: " << maxQueries << std::endl;
return 0;
}
#endif
Compilation message
minerals.cpp:28:18: error: 'std::mt19937 rand' redeclared as different kind of entity
28 | std::mt19937 rand(0);
| ^
In file included from /usr/include/c++/10/bits/std_abs.h:38,
from /usr/include/c++/10/cmath:47,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from minerals.cpp:1:
/usr/include/stdlib.h:453:12: note: previous declaration 'int rand()'
453 | extern int rand (void) __THROW;
| ^~~~
minerals.cpp: In function 'void findMatching(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | if (bound == a.size()) bound--;
| ~~~~~~^~~~~~~~~~~
minerals.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from minerals.cpp:1:
/usr/include/c++/10/bits/stl_algo.h: In instantiation of 'void std::shuffle(_RAIter, _RAIter, _UGenerator&&) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _UGenerator = int (&)()]':
minerals.cpp:38:42: required from here
/usr/include/c++/10/bits/stl_algo.h:3769:2: error: 'std::remove_reference<int (&)()>::type' {aka 'int()'} is not a class, struct, or union type
3769 | __uc_type;
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_algo.h:3797:37: error: 'std::remove_reference<int (&)()>::type' {aka 'int()'} is not a class, struct, or union type
3797 | const pair<__uc_type, __uc_type> __pospos =
| ^~~~~~~~
/usr/include/c++/10/bits/stl_algo.h:3797:37: error: 'std::remove_reference<int (&)()>::type' {aka 'int()'} is not a class, struct, or union type
