QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#843804#4218. Hidden GraphthangthangML 1ms3468kbC++201.2kb2025-01-05 02:39:382025-01-05 02:39:39

Judging History

你现在查看的是最新测评结果

  • [2025-01-05 02:39:39]
  • 评测
  • 测评结果:ML
  • 用时:1ms
  • 内存:3468kb
  • [2025-01-05 02:39:38]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second

using namespace std;
using ii = pair <int, int>;
using vi = vector <int>;

ii qry(vi &g){
    if (g.size() == 1) return ii(-1, -1);
    cout << "? " << g.size() << ' ';
    for (int u : g) cout << u << ' ';
    cout << endl;
    ii ans; cin >> ans.fi >> ans.se;
    return ans;
}

vector <ii> edges;

const int N = 2005;

bool e[N][N];

void add(int u, int v){
    e[u][v] = e[v][u] = 1;
    edges.pb({u, v});
}

void solve(vector <int> p){
    if (p.size() == 1) return;
    vector <int> s, t;
    for (int u : p){
        s.pb(u);
        auto [g, k] = qry(s);
        if (g != -1) s.pop_back(), t.pb(u), add(g, k);
    }

    for (int u : t){
        vi ask = {u};
        for (int v : s) if (!e[u][v]) ask.pb(v);
        auto [g, k] = qry(ask);
        if (g == -1) break;
        add(g, k);
    }

    solve(t);
}

int main(){
    int n; cin >> n;

    vector <int> p(n);
    iota(p.begin(), p.end(), 1);
    solve(p);

    cout << "! " << edges.size() << endl;
    for (auto [u, v]: edges) cout << u << ' ' << v << endl;


    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3468kb

input:

3
1 2
1 3
2 3

output:

? 2 1 2 
? 2 1 3 
? 2 2 3 
! 3
1 2
1 3
2 3

result:

ok correct

Test #2:

score: -100
Memory Limit Exceeded

input:

10
1 2
1 3
1 4
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
-1 -1
2 5
3 7
4 5
-1 -1
-1 -1

output:

? 2 1 2 
? 2 1 3 
? 2 1 4 
? 2 1 5 
? 3 1 5 6 
? 4 1 5 6 7 
? 5 1 5 6 7 8 
? 6 1 5 6 7 8 9 
? 7 1 5 6 7 8 9 10 
? 7 2 5 6 7 8 9 10 
? 7 3 5 6 7 8 9 10 
? 7 4 5 6 7 8 9 10 
? 2 2 3 
? 3 2 3 4 

result: