QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#155769#4218. Hidden GraphInsert_Username_HereWA 2ms3484kbC++201.4kb2023-09-02 04:31:442023-09-02 04:31:45

Judging History

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

  • [2023-09-02 04:31:45]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3484kb
  • [2023-09-02 04:31:44]
  • 提交

answer

#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
// Cope Counter = at least 147

pair<int, int> qry(set<int> pts) {
  cout << "? " << pts.size();
  for(int i : pts) cout << " " << i + 1;
  cout << "\n";
  cout.flush();
  pair<int, int> e;
  cin >> e.f >> e.s;
  if(e.f > e.s) swap(e.f, e.s);
  return e;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
  int n;
  cin >> n;
  bool vis[n];
  for(int i = 0; i < n; i++) vis[i] = 0;
  set<int> bk[n];
  set<int> cur;
  vector<pair<int, int>> edges;
  vis[0] = 1, bk[0].insert(0);
  for(int i = 1; i < n; i++) {
    for(int j = 0; j < n; j++) {
      if(bk[j].empty()) {
        if(!vis[i]) {
          vis[i] = 1;
          bk[j].insert(i);
        }
        break;
      }
      bk[j].insert(i);
      auto e = qry(bk[j]);
      if(e.f < 0) {
        if(!vis[i]) vis[i] = 1;
        else bk[j].erase(i);
        continue;
      }
      cur.clear();
      while(e.f >= 0) {
        edges.push_back(e);
        bk[j].erase(e.f - 1);
        cur.insert(e.f - 1);
        if(cur.size() < 2) break;
        e = qry(bk[j]);
      }
      bk[j].erase(i);
      for(auto k : cur) bk[j].insert(k);
    }
  }
  cout << "! " << edges.size() << "\n";
  for(auto i : edges) cout << i.f << " " << i.s << "\n";
  cout.flush();
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3484kb

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
Wrong Answer
time: 2ms
memory: 3424kb

input:

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

output:

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

result:

wrong answer read 9 edges but expected 12 edges