#include "chameleon.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void Solve(int N) {
auto ask = [&](vector<int> p) {
for (auto& x : p) x++;
return Query(p);
};
vector<int> done(N * 2);
for (int i = 0; i < N * 2; i++) {
done[i] = 1;
vector<int> q;
for (int j = 0; j < N * 2; j++) {
if (done[j]) q.emplace_back(j);
}
if (ask(q) == q.size()) continue;
done[i] = 0;
}
vector<int> p, q;
for (int i = 0; i < N * 2; i++) {
auto& which = done[i] ? p : q;
which.emplace_back(i);
}
vector<vector<int>> one_match(N * 2);
shuffle(p.begin(), p.end(), rng);
vector<int> cnt(2 * N);
for (int i : p) {
vector<int> a;
for (int j : q) {
if (cnt[j] < 3) a.emplace_back(j);
}
while (true) {
vector<int> rem(a.size());
iota(rem.begin(), rem.end(), 1);
for (int j = 1; j <= a.size(); j <<= 1) {
vector<int> what(1, i);
for (int k : rem) {
if (k & j) what.emplace_back(a[k - 1]);
}
int ok = (ask(what) != what.size());
vector<int> tmp;
for (int k : rem) {
if (((k & j) > 0) == ok) tmp.emplace_back(k);
}
swap(rem, tmp);
}
if (rem.size() == 0) break;
assert(rem.size() == 1);
int x = rem[0];
x--;
cnt[a[x]]++;
one_match[i].emplace_back(a[x]);
one_match[a[x]].emplace_back(i);
a.erase(a.begin() + x);
}
}
vector<int> answer(2 * N);
vector<int> love(2 * N);
vector<int> evol(2 * N);
fill(done.begin(), done.end(), 0);
for (int i = 0; i < 2 * N; i++) {
if (one_match[i].size() == 1) {
if (answer[i]) continue;
answer[i] = 1;
answer[one_match[i][0]] = 1;
Answer(i + 1, one_match[i][0] + 1);
} else {
int last = -1;
while (done[i] == 0) {
done[i] = 1;
int a = one_match[i][0];
int b = one_match[i][1];
int c = one_match[i][2];
if (last == -1) {
if (ask({i, a, b}) == 1) {
love[i] = c;
evol[c] = i;
} else if (ask({i, a, c}) == 1) {
love[i] = b;
evol[b] = i;
} else {
love[i] = a;
evol[a] = i;
}
} else {
if (last != a && ask({i, last, a}) == 1) {
int nxt = last ^ b ^ c;
love[i] = nxt;
evol[nxt] = i;
last = i;
i = nxt;
} else if (last != b && ask({i, last, b}) == 1) {
int nxt = last ^ a ^ c;
love[i] = nxt;
evol[nxt] = i;
last = i;
i = nxt;
} else {
int nxt = last ^ a ^ b;
love[i] = nxt;
evol[nxt] = i;
last = i;
i = nxt;
}
}
}
}
}
for (int i = 0; i < 2 * N; i++) {
if (answer[i]) continue;
for (int j : one_match[i]) {
if (j == love[i]) continue;
if (j == evol[i]) continue;
answer[i] = answer[j] = 1;
Answer(i + 1, j + 1);
}
}
}
Compilation message
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:20:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | if (ask(q) == q.size()) continue;
| ~~~~~~~^~~~~~~~~~~
chameleon.cpp:42:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int j = 1; j <= a.size(); j <<= 1) {
| ~~^~~~~~~~~~~
chameleon.cpp:47:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | int ok = (ask(what) != what.size());
| ~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
20 ms |
344 KB |
Output is correct |
| 4 |
Correct |
19 ms |
344 KB |
Output is correct |
| 5 |
Correct |
20 ms |
344 KB |
Output is correct |
| 6 |
Correct |
21 ms |
344 KB |
Output is correct |
| 7 |
Correct |
19 ms |
344 KB |
Output is correct |
| 8 |
Correct |
20 ms |
600 KB |
Output is correct |
| 9 |
Correct |
20 ms |
540 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 |
1 ms |
344 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [6] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 ms |
344 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [6] |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
30 ms |
344 KB |
Output is correct |
| 4 |
Correct |
31 ms |
344 KB |
Output is correct |
| 5 |
Correct |
30 ms |
344 KB |
Output is correct |
| 6 |
Correct |
31 ms |
792 KB |
Output is correct |
| 7 |
Correct |
32 ms |
344 KB |
Output is correct |
| 8 |
Correct |
31 ms |
528 KB |
Output is correct |
| 9 |
Correct |
31 ms |
520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
20 ms |
344 KB |
Output is correct |
| 4 |
Correct |
19 ms |
344 KB |
Output is correct |
| 5 |
Correct |
20 ms |
344 KB |
Output is correct |
| 6 |
Correct |
21 ms |
344 KB |
Output is correct |
| 7 |
Correct |
19 ms |
344 KB |
Output is correct |
| 8 |
Correct |
20 ms |
600 KB |
Output is correct |
| 9 |
Correct |
20 ms |
540 KB |
Output is correct |
| 10 |
Correct |
0 ms |
344 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
344 KB |
Output is correct |
| 13 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [6] |
| 14 |
Halted |
0 ms |
0 KB |
- |
