QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#405180 | #4218. Hidden Graph | iee | WA | 1ms | 3836kb | C++14 | 1.9kb | 2024-05-05 13:14:39 | 2024-05-05 13:14:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
pair<int, int> query(vector<int> v) {
cout << "?" << " " << v.size();
for (int x : v) {
cout << " " << x;
}
cout << endl;
int x, y;
cin >> x >> y;
return {x, y};
}
constexpr int N = 2005;
int n, p;
vector<int> e[N];
int deg[N];
int k;
int col[N];
vector<int> vec[N];
void coloring() {
set<pair<int, int>> se;
rep(u, 1, p - 1) {
se.insert({deg[u] = e[u].size(), u});
}
vector<int> del(p);
vector<int> seq;
while (se.size()) {
auto [d, u] = *se.begin();
se.erase(se.begin());
seq.push_back(u);
del[u] = 1;
for (int v : e[u]) {
if (!del[v]) {
se.erase({deg[v], v});
deg[v]--;
se.insert({deg[v], v});
}
}
}
reverse(seq.begin(), seq.end());
static bool dic[N], in[N];
rep(u, 1, p - 1) {
dic[u] = 0;
in[u] = 0;
}
for (int u : seq) {
for (int v : e[u]) {
if (dic[v]) {
in[col[v]] = 1;
}
}
int mex = 1;
while (in[mex]) {
mex++;
}
if (mex > k) k++;
col[u] = mex;
for (int v : e[u]) {
if (dic[v]) {
in[col[v]] = 0;
}
}
dic[u] = 1;
}
rep(i, 1, N - 1) {
vec[i].clear();
}
rep(u, 1, p - 1) {
vec[col[u]].push_back(u);
}
}
void solve(vector<int> nodes) {
nodes.push_back(p);
while (nodes.size() >= 2) {
auto [x, y] = query(nodes);
if (x == -1 && y == -1) return;
assert(x == p || y == p);
e[x].push_back(y);
e[y].push_back(x);
nodes.erase(find(nodes.begin(), nodes.end(), x ^ y ^ p));
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (p = 2; p <= n; p++) {
coloring();
rep(id, 1, k) solve(vec[id]);
}
vector<array<int, 2>> edges;
rep(u, 1, n) rep(v, 1, u - 1) if (e[u][v]) edges.push_back({u, v});
cout << "!" << " " << edges.size() << "\n";
for (auto [u, v] : edges) {
cout << u << " " << v << "\n";
}
cout << flush;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3836kb
input:
3 1 2 2 3 1 3
output:
? 2 1 2 ? 2 2 3 ? 2 1 3 ! 2 2 1 3 1
result:
wrong answer read 2 edges but expected 3 edges