#include "chameleon.h"
#include <vector>
#include <iostream>
#include <map>
#define ll int
using namespace std;
void Solve(int N) {
map <ll, ll> mp[2*N+1];
bool done[2*N+1];
ll A[2*N+1], B[2*N+1];
vector <ll> V[4], U, tmp;
for (int i=1; i<=2*N; ++i) {
A[i] = B[i] = -1;
done[i] = 0;
U.push_back(i);
}
for (int i=0; i<4; ++i) {
tmp.clear();
for (int j=0; j<U.size(); ++j) {
V[i].push_back(U[j]);
if (V[i].size() == 1) continue;
else if (Query(V[i]) != V[i].size()) {
tmp.push_back(U[j]);
V[i].pop_back();
}
}
swap(U, tmp);
}
for (int i=1; i<=2*N; ++i) {
for (int j=0; j<4; ++j) {
while (true) {
bool ok = 1;
tmp.clear();
for (auto u : V[j]) {
if (u == i) ok = 0;
else if (!mp[i].count(u)) tmp.push_back(u);
}
if (ok) {
tmp.push_back(i);
if (tmp.size() == 1 || Query(tmp) == tmp.size()) break;
ll l = 0, r = tmp.size()-1, mid;
while (l < r) {
mid = (l+r)/2;
U.clear();
for (int j=l; j<=mid; ++j) {
U.push_back(tmp[j]);
}
U.push_back(i);
if (Query(U) == U.size()) l = mid+1;
else r = mid;
}
++mp[i][tmp[l]];
++mp[tmp[l]][i];
swap(tmp[l], tmp[tmp.size()-1]);
tmp.pop_back();
}
else break;
}
}
}
for (int i=1; i<=2*N; ++i) {
tmp.clear();
for (auto [x, y] : mp[i]) {
tmp.push_back(x);
}
if (tmp.size() == 3) {
bool ok = 0;
for (int j=0; j<2; ++j) {
U = {tmp[j], tmp[(j+1)%3], i};
if (Query(U) == 1) {
ok = 1;
A[i] = tmp[(j+2)%3];
B[tmp[(j+2)%3]] = i;
break;
}
}
if (!ok) A[i] = tmp[1], B[tmp[1]] = i;
}
}
for (int i=1; i<=2*N; ++i) {
if (done[i]) continue;
for (auto [x, y] : mp[i]) {
if (x == A[i] || x == B[i]) continue;
Answer(i, x);
done[i] = done[x] = 1;
break;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |