QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#48635 | #4218. Hidden Graph | ckiseki# | TL | 0ms | 0kb | C++ | 1.3kb | 2022-09-14 20:34:47 | 2022-09-14 20:34:48 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
bool ask(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");
scanf("%d%d", &e.first, &e.second);
return not (e.first == -1 && e.second == -1);
}
vector<int> ask_edges(const vector<int> &v, int i) {
set<int> st(v.begin(), v.end());
st.insert(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);
}
return adj;
}
int main() {
// cin.tie(nullptr)->sync_with_stdio(false);
int n;
scanf("%d", &n);
vector<pair<int,int>> ans;
vector<vector<int>> buc;
for (int i = 1; i <= n; i++) {
bool found = false;
for (auto &v: buc) {
auto E = ask_edges(v, i);
if (not found && E.empty()) {
v.push_back(i);
found = true;
}
for (int j: E) {
ans.emplace_back(i, j);
}
}
if (not found) {
vector<int> v{i};
buc.emplace_back(v);
}
}
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: 0
Time Limit Exceeded
input:
3