This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "chameleon.h"
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
namespace {
int Check(const vector<int> &v, int n, int node) {
vector<int> u(v.begin(), v.begin() + n + 1);
u.emplace_back(node);
// dbg() "query: ";
// for (int x : u) dbg() x << ' ';
// dbg() endl;
int ans = Query(u);
// dbg() name(ans) endl;
return ans;
}
}
void Solve(int n) {
vector<vector<int>> adj(2 * n + 1);
vector<vector<int>> sides(2);
vector<int> col(2 * n + 1);
function<void(int, int)> Split = [&](int node, int c) {
sides[c].emplace_back(node);
col[node] = c;
for (int &x : adj[node]) {
if (col[x] == -1) {
Split(x, c ^ 1);
}
}
};
auto AddEdge = [&](int a, int b) {
adj[a].emplace_back(b);
adj[b].emplace_back(a);
dbg() name(a) name(b) endl;
};
for (int i = 1; i <= 2 * n; ++i) {
sides[0].clear(); sides[1].clear();
fill(col.begin(), col.end(), -1);
for (int j = 1; j < i; ++j) {
if (col[j] == -1) {
Split(j, 0);
}
}
// dbg() "parts: " << endl;
// for (int x : sides[0]) dbg() x << ' '; dbg() endl;
// for (int x : sides[1]) dbg() x << ' '; dbg() endl;
// dbg() endl;
for (int side = 0; side < 2; ++side) {
auto v = sides[side];
// dbg() name(i) name(side) name(v.size()) endl;
while (!v.empty()) {
// dbg() "enter\n";
int lo = 0, hi = v.size() - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (Check(v, mid, i) <= mid + 1) {
hi = mid - 1;
ans = mid;
} else {
lo = mid + 1;
}
}
if (ans == -1) break;
int x = v[ans];
AddEdge(i, x);
v = vector<int>(v.begin() + ans + 1, v.end());
}
}
}
int cnt_ans = 0;
vector<set<int>> link(2 * n + 1);
auto AddLink = [&](int x, int y) {
link[x].emplace(y);
if (link[y].count(x)) {
++cnt_ans;
Answer(x, y);
}
};
for (int i = 1; i <= 2 * n; ++i) {
if ((int)adj[i].size() == 1) {
AddLink(i, adj[i][0]);
continue;
}
assert((int)adj[i].size() == 3);
int x = Query({i, adj[i][0], adj[i][1]});
int y = Query({i, adj[i][0], adj[i][2]});
int z = Query({i, adj[i][1], adj[i][2]});
assert(x + y + z == 5);
if (x == 1) {
AddLink(i, adj[i][0]);
AddLink(i, adj[i][1]);
}
if (y == 1) {
AddLink(i, adj[i][0]);
AddLink(i, adj[i][2]);
}
if (z == 1) {
AddLink(i, adj[i][1]);
AddLink(i, adj[i][2]);
}
}
assert(cnt_ans == n);
}
# | 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... |