QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#330738 | #8056. Travel 2 | ucup-team1191# | AC ✓ | 149ms | 4284kb | C++14 | 2.5kb | 2024-02-17 18:20:14 | 2024-02-17 18:20:15 |
Judging History
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