#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> p(N), q(N);
iota(p.begin(), p.end(), 0);
iota(q.begin(), q.end(), N);
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 = N; j < N * 2; j++) {
if (cnt[j] < 3) a.emplace_back(j);
}
int repeat = 3;
while (repeat--) {
int low = 0, high = a.size() - 1;
while (low < high) {
int mid = low + high >> 1;
vector<int> what;
for (int j = low; j <= mid; j++) what.emplace_back(a[j]);
what.emplace_back(i);
if (ask(what) == what.size()) {
low = mid + 1;
} else {
high = mid;
}
}
cnt[a[high]]++;
one_match[i].emplace_back(a[high]);
one_match[a[high]].emplace_back(i);
a.erase(a.begin() + high);
}
}
vector<int> answer(2 * N);
vector<int> love(2 * N);
vector<int> evol(2 * N);
vector<int> done(2 * N);
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:29:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int mid = low + high >> 1;
| ~~~~^~~~~~
chameleon.cpp:33:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | if (ask(what) == what.size()) {
| ~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
