QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#496789 | #4218. Hidden Graph | haze | WA | 1ms | 3580kb | C++23 | 2.8kb | 2024-07-28 16:02:36 | 2024-07-28 16:02:36 |
Judging History
answer
/*
Author: Haze
2024/7/28
*/
#include <bits/stdc++.h>
#define irep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define drep(i, r, l) for(int i = (r); i >= (l); -- i)
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr);
using namespace std;
typedef long long ll;
inline ll readL() {
ll s = 0;
bool fl = false;
char ch = (char) getchar();
while (!isdigit(ch)) {
if (ch == '-')fl = true;
ch = (char) getchar();
}
while (isdigit(ch)) {
s = s * 10 + (ch ^ 48);
ch = (char) getchar();
}
return fl ? -s : s;
}
inline int read() {
return (int) (readL());
}
const int mod = 1000000000 + 7;
const int itinf = 1000000999;
const ll llinf = 2e18;
const int N = 500099;
array<int, 2> query(vector<int>&node){
if(node.size() == 1){
return {-1, -1};
}
cout << "? " << node.size();
for(int x : node){
cout << " " << x;
}
cout << endl;
array<int, 2>ar{};
cin >> ar[0] >> ar[1];
return ar;
}
int incol[N];
void solve() {
int n;
cin >> n;
vector<vector<int>>col = {{1}};
vector<array<int, 2>>edge;
//k = 1, n = 7, lim = 21
irep(u, 2, n){
int to = -1;
vector<int>vec;
vector<int>inf(col.size());
//1: not in
irep(i, 1, u)vec.push_back(i);
auto [i, j] = query(vec);
while(i != -1){
edge.push_back({i, j});
int v = i + j - u;
inf[incol[v]] = 1;
vec.erase(find(vec.begin(), vec.end(), i + j - u));
auto T = query(vec);
i = T[0], j = T[1];
}
int ok = 0;
irep(k, 0, col.size() - 1){
if(inf[k] == 0){
col[k].push_back(u);
ok = 1;
}
}
if(ok == 0){
col.push_back({u});
}
/*
irep(c, 0, col.size() - 1){
auto vec = col[c];
vec.push_back(u);
auto [i, j] = query(vec);
if(i == -1)to = c;
while(i != -1){
edge.push_back({i, j});
vec.erase(find(vec.begin(), vec.end(), i + j - u));
auto T = query(vec);
i = T[0], j = T[1];
}
}
*/
// if(to == -1){
// col.push_back({u});
// incol[u] = col.size() - 1;
// }
// else{
// col[to].push_back(u);
// incol[u] = to;
// }
}
cout << "! " << edge.size() << endl;
for(auto [u, v] : edge){
cout << u << ' ' << v << endl;
}
}
int main() {
// IOS
int T = 1;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3580kb
input:
3 1 2 1 2 1 2
output:
? 2 1 2 ? 3 1 2 3 ? 2 1 2 ! 3 1 2 1 2 1 2
result:
wrong answer incorrect graph