QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#48641 | #4218. Hidden Graph | ckiseki | WA | 3ms | 3796kb | C++ | 1.5kb | 2022-09-14 20:57:59 | 2022-09-14 20:58:01 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
bool ask(const set<int> &s, pair<int,int> &e) {
if (s.size() <= 1) {
return false;
}
printf("? %d", (int)s.size());
for (int x: s)
printf(" %d", x);
printf("\n");
fflush(stdout);
scanf("%d%d", &e.first, &e.second);
return not (e.first == -1 && e.second == -1);
}
vector<int> ask_edges(set<int> &st, int i) {
pair<int,int> e;
vector<int> adj;
while (ask(st, e)) {
int j = e.first == i ? e.second : e.first;
adj.push_back(j);
st.erase(j);
}
for (int j: adj) st.insert(j);
return adj;
}
vector<pair<int,int>> ans;
int pa[2001];
void gao(set<int> st) {
if (st.size() <= 1)
return;
vector<int> ind;
pair<int,int> e;
while (ask(st, e)) {
int i = e.first;
st.erase(i);
ind.push_back(i);
ans.emplace_back(e);
pa[i] = e.second;
}
for (int i: ind) {
int p = pa[i];
while (not st.count(p))
p = pa[p];
st.erase(p);
st.insert(i);
for (int j: ask_edges(st, i))
ans.emplace_back(i, j);
st.erase(i);
st.insert(p);
}
gao(set<int>(ind.begin(), ind.end()));
}
int main() {
// cin.tie(nullptr)->sync_with_stdio(false);
int n;
scanf("%d", &n);
set<int> st;
for (int i = 1; i <= n; i++)
st.insert(i);
gao(st);
printf("! %d\n", (int)ans.size());
for (auto [a, b]: ans)
printf("%d %d\n", a, b);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3796kb
input:
3 1 3 2 3 1 2
output:
? 3 1 2 3 ? 2 2 3 ? 2 1 2 ! 3 1 3 2 3 1 2
result:
ok correct
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3652kb
input:
10 1 4 2 6 3 7 4 10 -1 -1 -1 -1 2 5 -1 -1 3 9 3 8 3 10 -1 -1 4 5 4 8 -1 -1 1 3 -1 -1 1 4 1 2
output:
? 10 1 2 3 4 5 6 7 8 9 10 ? 9 2 3 4 5 6 7 8 9 10 ? 8 3 4 5 6 7 8 9 10 ? 7 4 5 6 7 8 9 10 ? 6 5 6 7 8 9 10 ? 6 1 5 6 7 8 9 ? 6 2 5 7 8 9 10 ? 5 2 7 8 9 10 ? 6 3 5 6 8 9 10 ? 5 3 5 6 8 10 ? 4 3 5 6 10 ? 3 3 5 6 ? 6 4 5 6 7 8 9 ? 5 4 6 7 8 9 ? 4 4 6 7 9 ? 4 1 2 3 4 ? 3 2 3 4 ? 3 1 2 4 ? 2 1 2 ! 13 1 4 ...
result:
wrong answer read 13 edges but expected 12 edges