QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#48635#4218. Hidden Graphckiseki#TL 0ms0kbC++1.3kb2022-09-14 20:34:472022-09-14 20:34:48

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-14 20:34:48]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-09-14 20:34:47]
  • 提交

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

output:


result: