QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#330738#8056. Travel 2ucup-team1191#AC ✓149ms4284kbC++142.5kb2024-02-17 18:20:142024-02-17 18:20:15

Judging History

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

  • [2024-02-17 18:20:15]
  • 评测
  • 测评结果:AC
  • 用时:149ms
  • 内存:4284kb
  • [2024-02-17 18:20:14]
  • 提交

answer

#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
typedef long long ll;

typedef unsigned long long ull;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    vector<int> init;
    vector<vector<int>> unused;
    vector<vector<int>> ed;
    vector<int> vis;
    auto initialize = [&](int u, int d) {
      while (init.size() <= u) {
        init.push_back(0);
        unused.push_back({});
        ed.push_back({});
        vis.push_back(0);
      }
      if (init[u]) {
        return;
      }
      init[u] = 1;
      ed[u].resize(d);
      unused[u].resize(d);
      iota(unused[u].begin(), unused[u].end(), 0);
    };
    int r, d;
    cin >> r >> d;
    --r;
    initialize(r, d);
    function<void(int, int)> dfs = [&](int u, int par) {
      // cout << "start " << u + 1 << endl;
      vis[u] = 1;
      int cur = u;
      while (!unused[cur].empty()) {
        // cout << "in cycle " << cur + 1 << ' ' << unused[cur].size() << endl;
        int dir = unused[cur].back();
        unused[cur].pop_back();
        cout << "> " << dir + 1 << endl;
        int x, d;
        cin >> x >> d;
        --x;
        initialize(x, d);
        ed[cur][dir] = x;
        cur = x;
      }
      assert(cur == u);
      for (int i = 0; i < (int)ed[u].size(); ++i) {
        int v = ed[u][i];
        if (!vis[v]) {
          // cout << "lol " << u + 1 << ' ' << ed[u].size() << endl;
          cout << "> " << i + 1 << endl;
          int x, d;
          cin >> x >> d;
          --x;
          assert(x == v);
          dfs(v, u);
        }
      }
      if (par != -1) {
        for (int i = 0; i < (int)ed[u].size(); ++i) {
          if (ed[u][i] == par) {
            cout << "> " << i + 1 << endl;
            int x, d;
            cin >> x >> d;
            --x;
            assert(x == par);
          }
        }
      }
    };
    dfs(r, -1);
    cout << "! ";
    for (int i = 0; i < (int)ed.size(); ++i) {
      for (int j : ed[i]) {
        if (i < j) {
          cout << i + 1 << ' ' << j + 1 << ' ';
        }
      }
    }
    cout << endl;
    string answer;
    cin >> answer;
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
1 1
2 1
1 1
2 1
1 1
Correct
1 3
4 2
2 2
4 2
1 3
3 1
1 3
2 2
1 3
2 2
4 2
2 2
1 3
3 1
1 3
Correct

output:

> 1
> 1
> 1
> 1
! 1 2 
> 3
> 2
> 2
> 1
> 2
> 1
> 1
> 1
> 1
> 2
> 2
> 1
> 2
> 1
! 1 2 1 3 1 4 2 4 

result:

ok correct

Test #2:

score: 0
Accepted
time: 149ms
memory: 3884kb

input:

1000
1 9
10 6
3 9
6 9
4 9
9 8
4 9
6 9
7 7
6 9
9 8
6 9
3 9
7 7
9 8
7 7
3 9
8 8
4 9
2 7
4 9
5 8
4 9
8 8
6 9
8 8
3 9
10 6
6 9
5 8
7 7
5 8
6 9
10 6
4 9
10 6
8 8
7 7
8 8
9 8
8 8
10 6
2 7
9 8
2 7
5 8
3 9
5 8
2 7
6 9
2 7
10 6
1 9
9 8
5 8
9 8
3 9
2 7
3 9
9 8
1 9
8 8
5 8
8 8
1 9
7 7
4 9
7 7
1 9
6 9
1 9
5 8
1...

output:

> 9
> 6
> 9
> 9
> 9
> 8
> 8
> 8
> 7
> 7
> 7
> 6
> 8
> 6
> 6
> 5
> 7
> 8
> 7
> 7
> 6
> 8
> 5
> 7
> 5
> 6
> 6
> 5
> 4
> 7
> 4
> 6
> 3
> 4
> 4
> 3
> 5
> 3
> 4
> 5
> 3
> 2
> 6
> 4
> 5
> 5
> 5
> 4
> 4
> 2
> 3
> 1
> 8
> 3
> 3
> 2
> 4
> 2
> 3
> 1
> 7
> 2
> 2
> 1
> 6
> 2
> 3
> 1
> 5
> 1
> 4
> 1
> 3
> 2
> 2
...

result:

ok correct

Test #3:

score: 0
Accepted
time: 116ms
memory: 3580kb

input:

500
1 19
20 6
12 7
18 7
12 7
20 6
17 10
20 6
9 7
3 7
9 7
15 8
9 7
17 10
9 7
20 6
15 8
19 7
15 8
5 7
14 9
10 9
14 9
5 7
15 8
8 4
18 7
8 4
15 8
6 7
7 11
2 8
7 11
12 7
7 11
19 7
10 9
4 8
10 9
19 7
7 11
14 9
7 11
10 9
2 8
10 9
7 11
6 7
14 9
18 7
2 8
18 7
14 9
2 8
11 8
2 8
14 9
6 7
15 8
16 7
17 10
16 7
1...

output:

> 19
> 6
> 7
> 7
> 6
> 5
> 10
> 4
> 7
> 7
> 6
> 8
> 5
> 9
> 4
> 3
> 7
> 7
> 6
> 7
> 9
> 9
> 8
> 6
> 5
> 4
> 6
> 3
> 4
> 7
> 11
> 8
> 10
> 5
> 9
> 6
> 8
> 8
> 7
> 5
> 8
> 7
> 7
> 6
> 7
> 5
> 6
> 6
> 6
> 5
> 6
> 4
> 5
> 5
> 8
> 4
> 4
> 5
> 3
> 7
> 8
> 6
> 4
> 4
> 3
> 5
> 2
> 2
> 6
> 7
> 5
> 3
> 4
> 7
...

result:

ok correct

Test #4:

score: 0
Accepted
time: 140ms
memory: 3920kb

input:

100
1 99
100 4
29 11
100 4
8 8
72 8
8 8
57 5
8 8
9 9
71 8
9 9
8 8
82 7
23 6
82 7
29 11
82 7
8 8
100 4
55 9
75 10
84 5
75 10
21 4
75 10
16 7
75 10
55 9
41 7
55 9
76 9
33 5
52 6
93 10
26 10
93 10
52 6
46 6
52 6
33 5
76 9
55 9
96 10
24 10
62 12
97 8
62 12
24 10
96 10
49 5
92 13
49 5
67 10
49 5
96 10
42...

output:

> 99
> 4
> 11
> 3
> 8
> 8
> 7
> 5
> 6
> 9
> 8
> 8
> 5
> 7
> 6
> 6
> 10
> 5
> 4
> 2
> 9
> 10
> 5
> 9
> 4
> 8
> 7
> 7
> 8
> 7
> 7
> 9
> 5
> 6
> 10
> 10
> 9
> 5
> 6
> 4
> 4
> 8
> 6
> 10
> 10
> 12
> 8
> 11
> 9
> 9
> 5
> 13
> 4
> 10
> 3
> 8
> 5
> 7
> 4
> 4
> 7
> 3
> 7
> 7
> 6
> 2
> 3
> 10
> 9
> 11
> 8
> ...

result:

ok correct

Test #5:

score: 0
Accepted
time: 109ms
memory: 3980kb

input:

10
1 999
1000 10
80 7
1000 10
856 9
1000 10
485 11
675 7
662 10
675 7
485 11
466 6
485 11
867 5
485 11
1000 10
674 4
752 6
436 7
752 6
674 4
611 8
525 6
611 8
371 8
34 9
371 8
528 6
530 11
528 6
371 8
611 8
606 6
791 11
606 6
33 6
606 6
467 7
606 6
732 6
34 9
119 10
34 9
732 6
628 12
455 7
628 12
73...

output:

> 999
> 10
> 7
> 9
> 9
> 8
> 11
> 7
> 10
> 6
> 10
> 6
> 9
> 5
> 8
> 7
> 4
> 6
> 7
> 5
> 3
> 8
> 6
> 7
> 8
> 9
> 7
> 6
> 11
> 5
> 6
> 6
> 6
> 11
> 5
> 6
> 4
> 7
> 3
> 6
> 8
> 10
> 7
> 5
> 12
> 7
> 11
> 4
> 2
> 5
> 7
> 11
> 9
> 10
> 8
> 9
> 4
> 11
> 3
> 8
> 7
> 9
> 13
> 8
> 6
> 7
> 9
> 10
> 7
> 9
> 8
...

result:

ok correct

Test #6:

score: 0
Accepted
time: 104ms
memory: 4284kb

input:

4
1 999
1000 25
684 16
987 21
684 16
14 23
767 14
333 26
767 14
374 21
767 14
14 23
684 16
261 22
917 21
952 20
917 21
261 22
684 16
902 23
656 21
902 23
684 16
269 16
62 16
450 29
930 19
450 29
62 16
269 16
684 16
1000 25
798 24
287 28
307 23
287 28
134 20
737 14
134 20
842 19
134 20
547 18
134 20
...

output:

> 999
> 25
> 16
> 21
> 15
> 23
> 14
> 26
> 13
> 21
> 12
> 22
> 14
> 22
> 21
> 20
> 20
> 21
> 13
> 23
> 21
> 22
> 12
> 16
> 16
> 29
> 19
> 28
> 15
> 15
> 11
> 24
> 24
> 28
> 23
> 27
> 20
> 14
> 19
> 19
> 18
> 18
> 17
> 26
> 15
> 13
> 14
> 25
> 19
> 23
> 18
> 22
> 17
> 24
> 23
> 14
> 22
> 19
> 21
> 18...

result:

ok correct

Test #7:

score: 0
Accepted
time: 137ms
memory: 4036kb

input:

4
1 199
200 102
92 110
200 102
12 94
184 90
12 94
23 104
12 94
200 102
189 101
80 96
189 101
50 94
189 101
188 101
110 97
188 101
189 101
96 99
98 95
96 99
189 101
200 102
88 102
172 100
88 102
66 108
117 106
66 108
150 105
36 104
150 105
144 109
150 105
46 102
150 105
66 108
88 102
143 91
40 91
127...

output:

> 199
> 102
> 110
> 101
> 94
> 90
> 93
> 104
> 92
> 100
> 101
> 96
> 100
> 94
> 99
> 101
> 97
> 100
> 98
> 99
> 95
> 98
> 97
> 99
> 102
> 100
> 101
> 108
> 106
> 107
> 105
> 104
> 104
> 109
> 103
> 102
> 102
> 106
> 100
> 91
> 91
> 103
> 90
> 108
> 89
> 90
> 86
> 97
> 99
> 96
> 85
> 89
> 99
> 101
> ...

result:

ok correct

Test #8:

score: 0
Accepted
time: 48ms
memory: 4260kb

input:

4
1 140
141 140
140 140
141 140
139 140
141 140
138 140
141 140
137 140
141 140
136 140
141 140
135 140
141 140
134 140
141 140
133 140
141 140
132 140
141 140
131 140
141 140
130 140
141 140
129 140
141 140
128 140
141 140
127 140
141 140
126 140
141 140
125 140
141 140
124 140
141 140
123 140
141 ...

output:

> 140
> 140
> 140
> 139
> 140
> 138
> 140
> 137
> 140
> 136
> 140
> 135
> 140
> 134
> 140
> 133
> 140
> 132
> 140
> 131
> 140
> 130
> 140
> 129
> 140
> 128
> 140
> 127
> 140
> 126
> 140
> 125
> 140
> 124
> 140
> 123
> 140
> 122
> 140
> 121
> 140
> 120
> 140
> 119
> 140
> 118
> 140
> 117
> 140
> 116
...

result:

ok correct

Test #9:

score: 0
Accepted
time: 47ms
memory: 4228kb

input:

4
1 2498
2499 2
2500 2498
2499 2
1 2498
2498 2
2500 2498
2498 2
1 2498
2497 2
2500 2498
2497 2
1 2498
2496 2
2500 2498
2496 2
1 2498
2495 2
2500 2498
2495 2
1 2498
2494 2
2500 2498
2494 2
1 2498
2493 2
2500 2498
2493 2
1 2498
2492 2
2500 2498
2492 2
1 2498
2491 2
2500 2498
2491 2
1 2498
2490 2
2500 ...

output:

> 2498
> 2
> 2498
> 1
> 2497
> 2
> 2497
> 1
> 2496
> 2
> 2496
> 1
> 2495
> 2
> 2495
> 1
> 2494
> 2
> 2494
> 1
> 2493
> 2
> 2493
> 1
> 2492
> 2
> 2492
> 1
> 2491
> 2
> 2491
> 1
> 2490
> 2
> 2490
> 1
> 2489
> 2
> 2489
> 1
> 2488
> 2
> 2488
> 1
> 2487
> 2
> 2487
> 1
> 2486
> 2
> 2486
> 1
> 2485
> 2
> 2...

result:

ok correct

Extra Test:

score: 0
Extra Test Passed