QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#110987 | #4218. Hidden Graph | Retrieve_72 | RE | 16ms | 3784kb | C++14 | 2.3kb | 2023-06-05 10:21:30 | 2023-06-05 10:21:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << var << "; "
#define int long long
int n, m, tot, ind[2010], lnd[2010], col[2010];
set<int> sub[2010], tmp; vector<int> g[2010];
void getsub(int n) {
set<pii> st; st.clear();
for (int i = 1; i <= n; i++)
st.insert(mp(ind[i], i));
memcpy(lnd, ind, sizeof lnd);
memset(col, 0, sizeof col); tot = 0;
while (st.size()) {
set<pii>::iterator it = st.begin(); st.erase(it);
int u = (*it).se; ind[u] = 0;
vector<int> c; c.clear();
for (int j = 0; j < g[u].size(); j++) {
if (col[g[u][j]]) c.pb(col[g[u][j]]);
if (ind[g[u][j]]) {
st.erase(mp(ind[g[u][j]], g[u][j])); ind[g[u][j]]--; st.insert(mp(ind[g[u][j]], g[u][j]));
}
}
sort(c.begin(), c.end());
int lst = 0, now = 0;
for (int i = 0; i < c.size(); i++)
if (c[i] > lst + 1) {
now = lst + 1; break;
} else lst = c[i];
col[u] = now;
if (!now) col[u] = now = ++tot;
}
memcpy(ind, lnd, sizeof lnd);
}
signed main() {
srand(time(0));
cin >> n;
tot = 1; sub[1].insert(1);
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= tot; j++) {
cout << "? " << sub[j].size() + 1 << " " << i << " ";
tmp = sub[j];
for (set<int>::iterator it = tmp.begin(); it != tmp.end(); it++) cout << *it << " "; cout << endl;
int u, v;
cin >> u >> v;
if (u != i) swap(u, v);
if (u == -1 && v == -1) {
}
else {
g[u].pb(v), g[v].pb(u); m++; ind[u]++, ind[v]++;
while (true) {
tmp.erase(v);
if (tmp.empty()) break;
cout << "? " << tmp.size() + 1 << " " << i << " ";
for (set<int>::iterator it = tmp.begin(); it != tmp.end(); it++) cout << *it << " "; cout << endl;
cin >> u >> v;
if (u != i) swap(u, v);
if (v != -1) {
g[u].pb(v), g[v].pb(u); m++; ind[u]++, ind[v]++;
} else break;
}
}
}
for (int i = 1; i <= tot; i++) sub[i].clear();
getsub(i);
for (int j = 1; j <= i; j++) sub[col[j]].insert(j);
}
cout << "! " << m << endl;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < g[i].size(); j++)
if (g[i][j] > i) cout << i << " " << g[i][j] << endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3776kb
input:
3 1 2 1 3 2 3
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ! 3 1 2 1 3 2 3
result:
ok correct
Test #2:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
10 1 2 1 3 -1 -1 -1 -1 1 4 4 5 2 5 -1 -1 -1 -1 2 6 -1 -1 -1 -1 -1 -1 3 7 -1 -1 -1 -1 -1 -1 -1 -1 3 8 4 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 10 4 10
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ? 3 4 2 3 ? 2 4 1 ? 3 5 2 4 ? 2 5 2 ? 2 5 3 ? 2 5 1 ? 4 6 2 3 4 ? 3 6 3 4 ? 2 6 1 ? 2 6 5 ? 4 7 2 3 4 ? 3 7 2 4 ? 2 7 6 ? 2 7 1 ? 2 7 5 ? 4 8 3 4 6 ? 3 8 4 6 ? 2 8 6 ? 3 8 2 7 ? 2 8 1 ? 2 8 5 ? 5 9 1 5 6 8 ? 2 9 7 ? 2 9 2 ? 2 9 3 ? 2 9 4 ? 5 10 1 ...
result:
ok correct
Test #3:
score: 0
Accepted
time: 3ms
memory: 3776kb
input:
5 2 1 3 1 3 2 4 1 4 2 -1 -1 -1 -1 5 1 5 2
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ? 2 4 1 ? 2 4 2 ? 2 4 3 ? 3 5 3 4 ? 2 5 1 ? 2 5 2 ! 7 1 2 1 3 1 4 1 5 2 3 2 4 2 5
result:
ok correct
Test #4:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
3 2 1 1 3 -1 -1
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ! 2 1 2 1 3
result:
ok correct
Test #5:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
6 1 2 3 1 3 2 -1 -1 4 2 3 4 4 5 -1 -1 2 5 3 5 -1 -1 -1 -1 3 6 -1 -1
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ? 2 4 1 ? 2 4 2 ? 2 4 3 ? 3 5 1 4 ? 2 5 1 ? 2 5 2 ? 2 5 3 ? 3 6 1 4 ? 2 6 2 ? 2 6 3 ? 2 6 5 ! 9 1 2 1 3 2 3 2 4 2 5 3 4 3 5 3 6 4 5
result:
ok correct
Test #6:
score: 0
Accepted
time: 7ms
memory: 3708kb
input:
27 -1 -1 3 1 3 2 -1 -1 -1 -1 -1 -1 3 5 -1 -1 1 5 2 5 -1 -1 6 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 8 -1 -1 -1 -1 6 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 9 -1 -1 10 8 -1 -1 -1 -1 -1 -1 -1 -1 4 11 6 11 -1 -1 5 11 -1 -1 -1 -1 -1 -1 -1 -1 1 11 12 11 -1 -1 5 12 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 8 13 -1 -1 -1 -...
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ? 2 4 1 ? 2 4 2 ? 2 4 3 ? 3 5 3 4 ? 2 5 4 ? 2 5 1 ? 2 5 2 ? 3 6 3 4 ? 2 6 1 ? 2 6 2 ? 2 6 5 ? 3 7 1 4 ? 3 7 3 6 ? 2 7 2 ? 2 7 5 ? 3 8 1 4 ? 2 8 4 ? 3 8 3 7 ? 3 8 5 6 ? 2 8 5 ? 2 8 2 ? 4 9 3 4 6 ? 4 9 5 7 8 ? 2 9 2 ? 2 9 1 ? 4 10 3 4 6 ? 4 10 5 7 8...
result:
ok correct
Test #7:
score: 0
Accepted
time: 9ms
memory: 3756kb
input:
47 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 3 5 4 -1 -1 -1 -1 -1 -1 -1 -1 7 5 -1 -1 -1 -1 7 6 -1 -1 -1 -1 5 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9 4 -1 -1 10 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 11 1 7 11 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 7 12 2 12 -1 -1 5 12 -1 -1 12 ...
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ? 2 4 1 ? 2 4 2 ? 2 4 3 ? 2 5 1 ? 2 5 2 ? 2 5 3 ? 2 5 4 ? 3 6 1 5 ? 2 6 2 ? 2 6 3 ? 2 6 4 ? 3 7 1 5 ? 2 7 1 ? 2 7 2 ? 2 7 6 ? 2 7 3 ? 2 7 4 ? 3 8 1 5 ? 2 8 1 ? 3 8 2 7 ? 2 8 3 ? 2 8 4 ? 2 8 6 ? 4 9 1 7 8 ? 3 9 2 5 ? 2 9 3 ? 2 9 4 ? 2 9 6 ? 4 10 ...
result:
ok correct
Test #8:
score: 0
Accepted
time: 16ms
memory: 3676kb
input:
38 -1 -1 -1 -1 -1 -1 4 1 -1 -1 -1 -1 4 5 -1 -1 3 5 1 5 4 6 -1 -1 -1 -1 -1 -1 -1 -1 4 7 2 7 -1 -1 7 5 6 7 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 11 4 -1 -1 -1 -1 -1 -1 -1 -1 11 1 -1 -1 12 8 12 7 -1 -1 11 12 -1 -1 -1 -1 -1 -1 -1 -1 -1...
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ? 2 4 1 ? 2 4 2 ? 2 4 3 ? 3 5 2 4 ? 2 5 2 ? 2 5 3 ? 2 5 1 ? 3 6 2 4 ? 2 6 2 ? 2 6 3 ? 2 6 1 ? 2 6 5 ? 3 7 2 4 ? 2 7 2 ? 2 7 3 ? 3 7 5 6 ? 2 7 6 ? 2 7 1 ? 4 8 2 5 6 ? 3 8 3 4 ? 2 8 1 ? 2 8 7 ? 4 9 5 6 8 ? 3 9 2 4 ? 2 9 3 ? 2 9 1 ? 2 9 7 ? 4 10 5 6...
result:
ok correct
Test #9:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
25 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 2 -1 -1 5 4 -1 -1 -1 -1 -1 -1 6 4 5 7 -1 -1 7 3 -1 -1 -1 -1 4 8 -1 -1 2 8 -1 -1 -1 -1 5 8 9 4 -1 -1 -1 -1 9 8 -1 -1 2 9 -1 -1 10 3 -1 -1 -1 -1 -1 -1 9 11 -1 -1 -1 -1 10 11 -1 -1 2 11 -1 -1 12 4 -1 -1 6 12 -1 -1 -1 -1 -1 -1 -1 -1 7 13 -1 -1 -1 -1 13 8 6 ...
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ? 2 4 1 ? 2 4 2 ? 2 4 3 ? 2 5 1 ? 2 5 2 ? 2 5 3 ? 2 5 4 ? 3 6 1 5 ? 2 6 3 ? 2 6 2 ? 2 6 4 ? 4 7 1 5 6 ? 3 7 1 6 ? 2 7 3 ? 2 7 2 ? 2 7 4 ? 4 8 1 4 7 ? 3 8 1 7 ? 2 8 2 ? 2 8 3 ? 2 8 6 ? 2 8 5 ? 4 9 1 4 7 ? 3 9 1 7 ? 3 9 3 5 ? 3 9 6 8 ? 2 9 6 ? 2 9 ...
result:
ok correct
Test #10:
score: 0
Accepted
time: 3ms
memory: 3704kb
input:
6 -1 -1 -1 -1 2 3 -1 -1 -1 -1 -1 -1 -1 -1 2 5 -1 -1 -1 -1 -1 -1 5 6
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ? 3 4 1 3 ? 2 4 2 ? 3 5 1 3 ? 2 5 4 ? 2 5 2 ? 3 6 1 2 ? 2 6 4 ? 2 6 3 ? 2 6 5 ! 3 2 3 2 5 5 6
result:
ok correct
Test #11:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
3 2 1 3 1 2 3
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ! 3 1 2 1 3 2 3
result:
ok correct
Test #12:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
3 2 1 3 1 -1 -1
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ! 2 1 2 1 3
result:
ok correct
Test #13:
score: 0
Accepted
time: 3ms
memory: 3640kb
input:
5 2 1 3 1 2 3 -1 -1 -1 -1 -1 -1 2 5 -1 -1 5 1 -1 -1
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ? 2 4 1 ? 2 4 2 ? 2 4 3 ? 3 5 2 4 ? 2 5 4 ? 2 5 1 ? 2 5 3 ! 5 1 2 1 3 1 5 2 3 2 5
result:
ok correct
Test #14:
score: 0
Accepted
time: 3ms
memory: 3708kb
input:
3 2 1 -1 -1 -1 -1
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ! 1 1 2
result:
ok correct
Test #15:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 3 -1 -1 2 5 3 5
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ? 2 4 1 ? 2 4 2 ? 2 4 3 ? 3 5 1 4 ? 2 5 2 ? 2 5 3 ! 3 2 5 3 4 3 5
result:
ok correct
Test #16:
score: -100
Runtime Error
input:
93 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
output:
? 2 2 1 ? 2 3 1 ? 2 3 2 ? 2 4 1 ? 2 4 2 ? 2 4 3 ? 2 5 1 ? 2 5 2 ? 2 5 3 ? 2 5 4 ? 2 6 1 ? 2 6 2 ? 2 6 3 ? 2 6 4 ? 2 6 5 ? 2 7 1 ? 2 7 2 ? 2 7 3 ? 2 7 4 ? 2 7 5 ? 2 7 6 ? 2 8 1 ? 2 8 2 ? 2 8 3 ? 2 8 4 ? 2 8 5 ? 2 8 6 ? 2 8 7 ? 2 9 1 ? 2 9 2 ? 2 9 3 ? 2 9 4 ? 2 9 5 ? 2...