QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#419370 | #2830. Data Structure | YuJiahe | AC ✓ | 85ms | 10964kb | C++23 | 2.9kb | 2024-05-23 21:01:16 | 2024-05-23 21:01:26 |
Judging History
answer
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
const int N = 200005;unordered_set<int> ept;
int n, m, o[N], a[N][2], ps[N][2], vi[N], ptr;
queue<pii> q1, q2, q3;vector<pii> ops;bool vv[N];
inline void clear(int i){o[i] = 0;}
inline void push(int i, int x){a[i][o[i] ++] = x, ps[x][ps[x][0] != 0] = i;}
inline int top(int i){return a[i][o[i] - 1];}
inline int pop(int i){ps[top(i)][ps[top(i)][0] != i] = 0;return a[i][-- o[i]];}
inline int size(int i){return o[i];}
inline void mov(int i, int j){ops.emplace_back(i, j), push(j, pop(i));}
inline void update(int v){if (vi[v] != 1) return;int x, y;
if (top(x = ps[v][0]) == v && top(y = ps[v][1]) == v){
if (size(x) + size(y) == 2) q1.emplace(x, y);
if (size(x) + size(y) == 3) q2.emplace(x, y);
if (size(x) + size(y) == 4) q3.emplace(x, y);vi[v] = 2;
}
}
inline void ers(int x){vi[x] = 0;while (ptr <= n && !vi[ptr]) ptr ++;}
int main(){
while (scanf("%d%d", &n, &m) != -1){
ops.clear(), ept.clear(), ptr = 1;
while (q1.size()) q1.pop();
while (q2.size()) q2.pop();
while (q3.size()) q3.pop();
for (int i = 1;i <= n;i ++) ps[i][0] = ps[i][1] = 0, vi[i] = 1, vv[i] = 0;
for (int i = 1, k;i <= m;i ++){
scanf("%d", &k), clear(i);if (!k) ept.insert(i);
for (int x;k --;) scanf("%d", &x), push(i, x);
if (size(i) == 2 && a[i][0] == a[i][1]) ers(top(i));
}
for (int rt = 1, p;rt <= n;rt ++) if (!vv[rt]){p = 0;
if (size(ps[rt][0]) == 1) p = ps[rt][0];
if (size(ps[rt][1]) == 1) p = ps[rt][1];
if (p) for (int u = rt, v, o;;p = o, u = v){
vv[u] = 1, update(u);
if (ps[u][0] != p) o = ps[u][0], v = a[o][a[o][0] == u];
if (ps[u][1] != p) o = ps[u][1], v = a[o][a[o][0] == u];
if (size(o) == 1) break;
}
}
for (int rt = 1, p;rt <= n;rt ++) if (!vv[rt]){
if (ps[rt][0] == ps[rt][1]) continue;p = ps[rt][0];
for (int u = rt, v, o;!vv[u];p = o, u = v){vv[u] = 1, update(u);
if (ps[u][0] != p) o = ps[u][0], v = a[o][a[o][0] == u];
if (ps[u][1] != p) o = ps[u][1], v = a[o][a[o][0] == u];
}
}
while (ptr <= n){
if (q1.size()){
auto [x, y] = q1.front();q1.pop();
ers(top(x)), mov(x, y), ept.insert(x);
}
else if (q2.size()){
auto [x, y] = q2.front();q2.pop();
if (size(x) > size(y)) swap(x, y);
ers(top(x)), mov(y, x), update(top(y));
}
else if (q3.size()){if (ept.empty()) goto Nxt;
auto [x, y] = q3.front();q3.pop();
int z = *ept.begin();ept.erase(z), ers(top(x));
mov(x, z), mov(y, z), update(top(x)), update(top(y));
}
else {if (ept.empty()) goto Nxt;
int x = ps[ptr][0], y = *ept.begin();
ept.erase(y), mov(x, y), update(top(x));
}
}printf("%d\n", ops.size());
for (auto [x, y] : ops) printf("%d %d\n", x, y);
continue;Nxt:printf("-1\n");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5860kb
input:
2 3 2 1 2 2 1 2 0 1 1 2 1 1 3 4 2 1 3 2 2 3 1 1 1 2
output:
3 1 3 2 3 1 2 0 -1
result:
ok 3 cases passed. max #moves/#balls = 1.500000000
Test #2:
score: 0
Accepted
time: 1ms
memory: 8168kb
input:
1 2 1 1 1 1 1 3 1 1 0 1 1 1 4 1 1 1 1 0 0 1 1 2 1 1 1 2 2 1 1 0 1 3 0 0 2 1 1
output:
1 1 2 1 1 3 1 1 2 0 0 0
result:
ok 6 cases passed. max #moves/#balls = 1.000000000
Test #3:
score: 0
Accepted
time: 1ms
memory: 7828kb
input:
2 4 1 1 1 2 1 2 1 1 2 5 1 1 1 2 0 1 1 1 2 2 6 0 1 1 0 1 1 1 2 1 2 2 4 1 2 1 1 1 1 1 2 2 5 1 1 0 1 2 1 2 1 1 2 6 1 2 0 1 1 0 1 1 1 2 2 4 1 1 1 2 1 2 1 1 2 5 0 1 2 1 1 1 1 1 2 2 6 1 1 0 1 2 1 2 0 1 1 2 3 2 2 1 1 1 1 2 2 4 2 2 1 1 1 0 1 2 2 5 1 1 0 1 2 2 1 2 0 2 3 1 2 2 1 2 1 1 2 4 1 1 2 2 1 1 2 0 2 5 ...
output:
2 1 4 2 3 2 1 4 2 5 2 2 4 5 6 2 2 3 1 4 2 1 5 3 4 2 3 5 1 6 2 1 4 2 3 2 3 4 2 5 2 1 6 3 4 2 1 2 1 3 2 1 2 1 4 2 4 3 1 4 2 2 1 2 3 2 2 1 2 3 2 1 3 1 4 -1 3 2 1 3 1 2 3 3 2 3 4 3 2 4 -1 3 1 3 2 1 3 2 3 1 4 2 1 4 2 1 2 3 1 3 4 1 1 4 0 0 0
result:
ok 27 cases passed. max #moves/#balls = 1.500000000
Test #4:
score: 0
Accepted
time: 1ms
memory: 6124kb
input:
3 6 1 1 1 2 1 2 1 3 1 3 1 1 3 7 1 3 0 1 2 1 2 1 1 1 1 1 3 3 8 0 1 3 1 2 0 1 1 1 1 1 2 1 3 3 6 1 3 1 3 1 2 1 1 1 1 1 2 3 7 1 1 1 3 1 1 1 2 1 2 1 3 0 3 8 1 1 1 2 0 1 3 1 2 0 1 3 1 1 3 6 1 3 1 1 1 2 1 3 1 2 1 1 3 7 1 1 1 2 0 1 1 1 3 1 3 1 2 3 8 1 2 1 1 1 3 1 2 0 1 3 0 1 1 3 6 1 2 1 2 1 3 1 1 1 1 1 3 3 ...
output:
3 1 6 2 3 4 5 3 5 6 3 4 1 7 3 5 6 3 7 2 8 3 4 5 3 6 1 2 3 1 3 4 5 2 6 3 1 8 2 5 4 7 3 2 6 3 5 1 4 3 1 4 2 7 5 6 3 2 8 1 4 3 6 3 4 5 1 2 3 6 3 2 5 4 7 3 6 3 3 4 1 2 5 8 3 1 6 2 5 3 4 3 5 6 1 3 4 7 3 6 7 2 5 4 8 3 1 2 3 6 4 5 3 1 3 5 6 2 7 3 3 7 2 4 6 8 3 1 5 4 6 2 3 3 4 7 1 5 2 3 3 1 6 5 7 4 8 3 4 6 ...
result:
ok 180 cases passed. max #moves/#balls = 1.333333333
Test #5:
score: 0
Accepted
time: 0ms
memory: 7900kb
input:
4 8 1 3 1 3 1 4 1 1 1 2 1 1 1 4 1 2 4 9 1 3 0 1 2 1 1 1 4 1 1 1 4 1 2 1 3 4 10 1 1 1 3 1 3 1 2 1 2 0 1 1 1 4 1 4 0 4 8 1 4 1 3 1 2 1 2 1 1 1 4 1 1 1 3 4 9 1 4 1 3 1 1 1 3 1 4 1 2 1 1 1 2 0 4 10 1 4 1 1 1 2 1 3 0 0 1 2 1 1 1 3 1 4 4 8 1 2 1 4 1 3 1 4 1 2 1 3 1 1 1 1 4 9 1 1 1 4 1 3 1 2 1 3 1 2 0 1 4 ...
output:
4 4 6 5 8 1 2 3 7 4 4 6 3 8 1 9 5 7 4 1 7 4 5 2 3 8 9 4 5 7 3 4 2 8 1 6 4 3 7 6 8 2 4 1 5 4 2 8 3 7 4 9 1 10 4 7 8 1 5 3 6 2 4 4 1 9 4 6 3 5 2 8 4 4 7 2 3 8 10 5 6 4 1 3 4 7 2 8 5 6 4 2 9 1 7 5 6 3 4 4 2 10 1 9 4 5 3 8 4 2 5 1 3 4 8 6 7 4 1 5 3 8 4 9 2 7 4 3 6 2 9 5 7 1 8 4 2 8 6 7 1 5 3 4 4 2 8 6 7...
result:
ok 1575 cases passed. max #moves/#balls = 1.500000000
Test #6:
score: 0
Accepted
time: 27ms
memory: 5792kb
input:
5 10 1 1 1 4 1 2 1 4 1 5 1 2 1 3 1 5 1 1 1 3 5 11 1 1 1 3 1 1 1 2 1 5 1 2 0 1 5 1 4 1 3 1 4 5 12 1 2 0 1 1 1 5 1 2 1 4 1 3 1 4 0 1 5 1 3 1 1 5 10 1 3 1 5 1 1 1 1 1 2 1 4 1 4 1 5 1 2 1 3 5 11 1 3 1 5 1 2 1 2 1 4 1 3 1 1 1 1 0 1 4 1 5 5 12 1 3 1 4 1 2 0 1 5 1 1 1 2 1 1 1 4 1 5 0 1 3 5 10 1 4 1 5 1 3 1...
output:
5 1 9 3 6 7 10 2 4 5 8 5 1 3 4 6 2 10 9 11 5 8 5 3 12 1 5 7 11 6 8 4 10 5 3 4 5 9 1 10 6 7 2 8 5 7 8 3 4 1 6 5 10 2 11 5 6 8 3 7 1 12 2 9 5 10 5 4 7 8 9 3 10 1 5 2 6 5 2 4 1 6 5 7 8 9 3 11 5 1 7 2 3 10 11 8 9 4 5 5 8 10 4 5 6 7 2 9 1 3 5 6 7 1 11 4 5 2 3 8 9 5 2 6 4 11 8 9 1 7 3 10 5 7 8 1 10 4 5 3 ...
result:
ok 17010 cases passed. max #moves/#balls = 1.400000000
Test #7:
score: 0
Accepted
time: 27ms
memory: 8164kb
input:
6 11 1 5 1 6 1 2 1 4 1 1 1 5 1 4 1 3 1 6 2 2 3 1 1 6 9 1 6 2 1 1 2 4 4 1 2 2 6 2 0 2 5 3 0 2 5 3 6 6 2 4 4 2 5 6 2 3 6 2 2 2 2 3 5 2 1 1 6 8 2 2 1 2 3 4 1 6 2 1 2 2 3 5 0 1 6 2 4 5 6 9 1 6 1 4 1 3 1 5 2 3 1 2 4 2 2 2 1 1 6 1 5 6 7 1 4 2 2 3 2 1 6 2 1 4 2 6 2 2 5 5 1 3 6 8 1 2 2 3 5 1 1 2 4 4 0 2 5 1...
output:
6 5 11 4 7 1 6 2 9 10 8 3 10 5 5 4 1 5 7 1 9 1 7 9 -1 8 3 7 5 3 8 3 2 8 2 5 1 2 4 1 2 4 7 4 9 1 8 5 1 7 1 3 5 6 7 2 6 5 2 7 4 1 5 2 3 5 3 4 5 6 3 7 1 2 6 8 7 2 8 5 1 9 2 6 3 10 5 7 8 11 6 1 6 1 5 3 1 4 1 2 4 2 3 -1 6 7 12 2 3 1 11 5 10 6 8 4 9 3 7 6 5 7 3 5 8 1 6 7 6 1 9 4 7 3 4 5 3 8 3 5 8 6 5 9 2 ...
result:
ok 14285 cases passed. max #moves/#balls = 1.500000000
Test #8:
score: 0
Accepted
time: 23ms
memory: 5888kb
input:
7 10 2 4 3 1 1 2 2 2 2 4 3 2 7 7 2 6 6 2 5 5 0 1 1 0 7 12 1 2 1 6 1 6 1 5 2 4 1 1 1 2 4 3 1 7 1 5 1 3 1 2 1 7 7 15 1 4 1 6 1 2 1 4 1 6 1 5 1 7 1 1 1 3 0 1 7 1 5 1 1 1 3 1 2 7 7 2 7 3 2 2 3 2 5 7 2 1 1 2 6 6 2 2 5 2 4 4 7 12 2 3 2 1 7 2 6 3 1 4 1 2 1 5 1 1 1 4 1 5 1 1 1 6 1 7 7 14 2 3 5 0 1 2 1 6 1 4...
output:
4 2 9 1 2 4 2 1 4 7 1 11 4 9 2 3 8 12 5 6 7 10 5 7 7 8 13 3 15 9 14 1 4 6 12 2 5 7 11 -1 7 7 10 4 8 6 9 2 12 1 5 3 1 3 11 7 10 13 3 14 5 8 4 12 9 11 1 7 1 6 7 1 6 3 1 10 1 7 3 8 10 4 8 4 7 7 5 12 7 10 8 9 1 4 2 11 6 2 3 6 7 2 10 4 6 5 11 3 4 7 4 3 5 7 9 7 2 7 5 9 4 1 4 6 8 4 10 4 8 10 7 4 5 3 8 2 9 ...
result:
ok 12500 cases passed. max #moves/#balls = 1.428571429
Test #9:
score: 0
Accepted
time: 28ms
memory: 6128kb
input:
8 16 1 2 0 1 5 1 8 1 1 1 5 2 4 4 1 8 1 6 1 1 1 2 0 2 7 7 1 3 1 6 1 3 8 13 1 8 1 4 1 2 1 6 2 1 3 2 1 3 1 7 1 2 1 5 1 6 1 8 2 4 5 1 7 8 9 2 1 3 2 4 5 2 7 2 2 7 8 2 4 8 2 1 6 2 5 2 2 6 3 0 8 17 1 1 1 4 1 3 1 7 1 2 1 2 1 7 1 5 1 3 1 4 1 6 1 8 1 5 1 6 1 8 1 1 0 8 15 1 6 1 4 0 1 5 1 7 1 3 1 2 1 8 1 6 1 7 ...
output:
6 5 10 1 11 14 16 3 6 9 15 4 8 9 3 8 4 10 7 13 1 11 12 9 2 12 5 2 6 2 5 6 -1 8 1 16 5 6 3 9 2 10 8 13 11 14 4 7 12 15 9 7 15 6 14 1 9 5 10 8 12 11 8 13 8 2 11 4 13 9 3 1 7 1 4 3 5 7 4 5 8 4 9 4 2 8 2 9 7 2 6 1 2 8 2 10 1 5 8 4 10 4 5 8 7 9 2 11 4 16 3 8 10 12 5 13 1 6 14 15 10 5 8 3 5 7 5 4 3 4 7 1 ...
result:
ok 11111 cases passed. max #moves/#balls = 1.500000000
Test #10:
score: 0
Accepted
time: 28ms
memory: 5840kb
input:
9 13 1 2 2 4 5 2 5 4 2 2 9 1 8 1 3 1 1 1 3 1 1 2 7 6 1 9 1 8 2 7 6 9 13 1 4 2 5 6 2 7 5 2 9 3 1 4 2 9 7 0 2 8 6 2 1 3 0 1 2 1 2 2 8 1 9 18 1 4 1 7 1 7 1 9 1 8 1 8 1 2 1 3 1 6 1 2 1 1 1 3 1 5 1 1 1 6 1 5 1 4 1 9 9 13 0 2 6 7 2 2 2 1 3 2 6 8 2 9 1 2 1 4 1 9 2 8 7 0 1 4 1 3 2 5 5 9 17 1 9 2 1 3 1 2 1 5...
output:
11 7 9 6 8 5 12 4 11 1 4 10 1 13 1 10 13 2 10 3 2 10 3 11 11 12 1 5 2 1 8 1 3 2 6 3 4 11 9 11 4 6 13 9 8 13 9 11 14 7 10 8 12 1 17 13 16 9 15 2 3 5 6 4 18 8 4 12 7 11 6 7 6 8 2 6 9 6 5 9 2 5 9 3 11 4 10 9 17 15 16 5 14 1 13 2 7 6 12 2 6 13 5 4 6 4 9 6 5 9 1 5 10 5 1 10 7 1 11 7 1 11 2 1 8 2 1 8 8 5 ...
result:
ok 10000 cases passed. max #moves/#balls = 1.444444444
Test #11:
score: 0
Accepted
time: 28ms
memory: 5808kb
input:
10 19 1 1 1 3 1 10 1 8 1 1 1 4 1 2 1 2 1 5 1 7 1 5 2 6 6 1 7 1 3 1 4 1 9 1 10 1 8 1 9 10 19 1 8 1 10 2 7 7 1 2 1 5 1 9 1 1 0 1 6 1 9 1 1 1 6 1 5 0 1 2 1 10 2 4 4 2 3 3 1 8 10 10 2 5 5 2 2 3 2 8 4 2 2 7 2 6 9 2 3 10 2 10 1 2 6 4 2 7 8 2 9 1 10 19 1 4 1 5 1 4 1 9 2 3 9 1 10 1 1 1 7 1 6 1 8 1 10 1 5 1 ...
output:
9 1 5 7 8 2 14 6 15 9 11 10 13 4 18 16 19 3 17 7 7 11 4 15 5 13 9 12 1 19 6 10 2 16 -1 10 7 17 13 16 1 3 2 12 9 14 8 18 10 15 6 11 5 4 5 19 11 4 19 10 12 15 16 3 17 1 9 8 14 5 6 5 13 7 5 18 7 5 18 7 8 16 12 18 6 13 10 14 1 3 17 19 5 9 10 9 16 4 6 8 12 7 14 10 17 2 15 11 18 3 13 5 3 1 5 10 8 12 10 13...
result:
ok 9090 cases passed. max #moves/#balls = 1.500000000
Test #12:
score: 0
Accepted
time: 29ms
memory: 7880kb
input:
11 15 2 11 11 2 3 3 1 2 0 2 8 5 1 2 2 6 4 2 4 5 1 1 1 1 1 9 1 10 2 8 6 2 7 7 2 9 10 11 17 2 4 8 1 11 2 6 7 1 9 1 9 1 5 1 2 1 2 1 5 1 10 1 3 1 1 1 11 2 10 8 1 1 2 3 7 2 4 6 11 21 1 10 1 6 1 3 1 9 1 8 1 1 1 5 1 10 1 5 1 4 1 8 1 9 1 11 1 6 1 11 1 7 1 1 1 4 2 2 2 1 7 1 3 11 15 1 5 1 1 1 2 2 3 3 2 10 7 0...
output:
9 9 10 3 6 15 12 11 15 5 11 8 11 7 8 13 7 5 13 13 12 15 7 8 6 9 4 5 2 13 3 2 16 2 11 16 17 3 1 11 14 11 1 17 10 14 10 6 17 3 21 10 18 7 9 2 14 16 20 5 11 4 12 1 8 13 15 11 2 9 1 10 15 3 12 11 8 12 8 15 13 8 14 8 7 14 5 7 5 13 10 7 10 14 18 3 6 12 17 4 15 2 19 9 13 16 8 5 11 5 16 11 7 10 7 12 1 7 4 7...
result:
ok 8333 cases passed. max #moves/#balls = 1.363636364
Test #13:
score: 0
Accepted
time: 29ms
memory: 6128kb
input:
12 25 1 9 1 10 1 4 1 7 1 5 1 3 1 6 1 1 1 12 1 3 1 2 1 9 1 11 1 2 0 1 10 1 7 1 12 1 11 1 4 1 6 1 5 1 1 1 8 1 8 12 19 1 2 1 12 2 8 8 2 1 3 0 2 3 4 1 5 2 11 11 2 1 5 2 9 6 1 12 1 7 1 7 2 6 9 1 2 1 4 1 10 1 10 0 12 14 2 2 4 2 8 8 2 1 3 2 9 9 2 6 12 2 6 1 0 2 10 10 2 5 5 2 3 12 0 2 4 7 2 7 2 2 11 11 12 1...
output:
12 8 23 11 14 6 10 3 20 5 22 7 21 4 17 24 25 1 12 2 16 13 19 9 18 11 1 15 12 13 17 18 2 11 6 16 9 7 4 6 4 9 10 2 14 10 2 14 9 5 11 10 11 3 10 6 3 5 6 1 5 13 1 12 13 5 12 10 8 13 14 13 3 8 1 3 7 5 12 5 1 7 4 12 6 4 6 14 12 11 24 7 14 5 19 1 10 12 21 16 25 2 6 4 20 8 22 9 17 3 13 15 18 11 2 12 4 5 13 ...
result:
ok 7692 cases passed. max #moves/#balls = 1.416666667
Test #14:
score: 0
Accepted
time: 29ms
memory: 5844kb
input:
13 15 2 8 8 2 6 6 2 1 1 2 3 3 2 11 11 2 2 5 2 5 13 1 4 1 12 2 2 13 1 12 2 10 10 1 4 2 9 9 2 7 7 13 21 2 11 11 1 9 1 2 1 9 1 13 1 1 1 13 1 5 2 12 8 2 7 7 1 5 1 6 1 6 2 4 3 1 1 0 2 10 10 1 2 2 4 3 0 2 8 12 13 24 1 8 1 7 1 6 1 3 1 5 1 9 1 2 1 13 1 2 1 12 2 10 10 1 3 1 1 1 8 1 4 1 12 1 6 1 5 1 7 1 4 2 1...
output:
6 8 13 9 11 7 9 10 9 6 7 6 10 12 6 15 3 18 8 11 12 13 2 4 5 7 14 5 19 5 14 19 9 14 21 9 14 21 11 13 23 7 9 4 12 15 20 5 18 3 17 2 19 1 14 6 24 10 16 8 22 12 8 15 13 20 3 17 4 16 1 11 2 14 10 6 9 7 9 10 5 9 19 9 5 19 12 10 16 1 27 9 18 12 26 4 20 5 23 8 14 3 6 7 17 11 19 2 25 21 22 13 3 17 11 15 2 9 ...
result:
ok 7142 cases passed. max #moves/#balls = 1.384615385
Test #15:
score: 0
Accepted
time: 29ms
memory: 5868kb
input:
14 24 1 3 1 11 1 2 1 7 1 5 0 1 11 2 4 8 2 12 5 2 9 4 1 3 1 10 2 12 9 1 1 0 2 13 13 1 2 1 7 1 6 1 10 1 14 1 1 1 6 2 8 14 14 27 1 8 1 10 1 1 1 1 1 12 1 14 1 6 1 11 1 5 1 12 1 7 1 4 1 10 1 14 1 7 1 9 1 2 1 6 1 11 1 9 2 3 3 1 2 1 4 1 13 1 8 1 5 1 13 14 22 1 14 2 7 5 1 3 1 10 1 9 1 9 2 13 5 2 12 2 2 6 6 ...
output:
13 14 22 3 17 1 11 19 23 4 18 12 20 2 7 9 5 24 21 8 24 10 8 13 10 9 13 13 3 4 17 22 12 23 9 26 7 18 11 15 1 25 16 20 2 13 8 19 5 10 24 27 6 14 12 19 22 3 15 5 6 4 21 14 20 1 17 8 13 8 11 2 8 7 8 10 2 7 10 13 4 15 16 25 6 21 7 12 11 18 2 19 14 17 1 3 9 10 8 20 13 8 23 8 13 23 14 8 19 4 9 7 23 3 28 22...
result:
ok 6666 cases passed. max #moves/#balls = 1.357142857
Test #16:
score: 0
Accepted
time: 25ms
memory: 7880kb
input:
15 22 0 2 6 13 1 13 1 4 1 8 1 8 0 2 10 3 2 11 15 2 15 7 1 5 2 2 12 2 11 12 1 6 1 7 2 9 9 1 5 2 1 1 2 3 10 2 14 14 1 4 1 2 15 24 1 2 1 4 2 8 11 1 9 0 1 1 2 5 5 1 9 2 6 6 1 12 1 3 1 3 2 7 13 2 11 10 1 14 1 12 2 10 4 1 15 2 8 7 1 2 0 1 1 1 15 2 13 14 15 24 0 1 14 1 14 2 1 1 1 10 1 12 1 5 2 10 6 1 13 1 ...
output:
14 4 21 11 17 5 6 10 15 2 3 2 14 9 10 12 2 13 2 12 22 9 13 8 9 19 8 9 19 13 6 22 1 20 11 12 4 8 10 16 18 23 17 2 24 15 14 17 13 24 3 14 19 13 3 19 12 10 13 7 12 15 16 23 24 6 22 9 14 2 3 8 18 5 8 17 5 19 5 17 19 15 6 17 10 6 16 6 5 16 11 3 15 3 10 15 2 10 14 10 2 5 12 14 11 12 7 11 13 11 7 13 16 15 ...
result:
ok 6250 cases passed. max #moves/#balls = 1.400000000
Test #17:
score: 0
Accepted
time: 29ms
memory: 8164kb
input:
16 23 1 3 1 9 0 1 9 1 14 1 4 2 5 14 1 10 2 16 5 2 6 6 2 1 1 2 16 11 2 12 12 1 2 1 4 0 2 8 8 2 11 13 1 7 1 10 2 2 15 2 3 15 2 7 13 16 29 0 1 6 1 3 1 7 1 14 1 12 1 9 1 3 1 10 1 14 1 13 1 2 2 6 9 1 4 1 2 2 5 1 1 8 1 16 1 4 2 1 5 1 11 1 7 2 8 10 1 15 1 12 1 11 1 15 1 16 1 13 16 28 1 13 1 8 1 9 1 12 2 15...
output:
14 6 15 2 4 8 20 7 5 9 7 21 8 22 8 14 21 1 22 18 1 23 1 19 23 12 18 9 12 17 12 15 3 8 14 19 4 22 21 26 6 25 11 29 5 10 24 27 18 28 13 7 2 13 23 9 17 23 16 2 20 16 2 20 16 13 20 7 25 16 27 6 28 19 26 12 23 9 22 2 14 10 21 4 17 1 11 24 3 15 24 5 1 18 1 5 18 15 15 21 10 19 8 14 12 18 1 13 7 23 9 1 17 1...
result:
ok 5882 cases passed. max #moves/#balls = 1.375000000
Test #18:
score: 0
Accepted
time: 29ms
memory: 5924kb
input:
17 33 1 12 2 15 4 1 5 1 13 0 1 6 1 17 1 16 1 7 1 11 1 13 1 17 1 1 1 11 1 12 1 9 1 3 1 7 1 5 1 3 1 2 1 9 1 14 2 15 4 1 1 1 10 1 10 1 8 1 2 1 16 1 14 1 8 1 6 17 23 1 9 2 13 17 1 3 1 13 1 10 2 15 16 2 12 12 2 14 4 2 5 15 1 9 1 7 1 6 2 8 8 1 2 2 4 11 1 11 2 16 5 2 2 10 1 3 1 6 2 1 1 2 14 17 1 7 17 20 2 ...
output:
18 13 25 21 29 17 20 3 19 6 33 9 18 28 32 16 22 26 27 10 14 1 15 4 11 23 31 8 30 7 12 2 7 24 7 2 24 16 3 19 12 20 11 23 1 10 18 5 14 18 15 16 8 15 2 14 22 14 2 4 8 22 9 8 17 9 6 17 6 8 15 6 17 4 6 13 6 4 13 11 4 20 4 5 11 16 5 14 16 9 14 9 20 2 9 18 2 10 18 9 10 18 25 28 9 21 5 11 13 31 4 24 12 20 2...
result:
ok 5555 cases passed. max #moves/#balls = 1.352941176
Test #19:
score: 0
Accepted
time: 25ms
memory: 5836kb
input:
18 19 2 8 5 2 7 11 2 1 13 2 2 2 0 2 17 11 2 14 6 2 18 18 2 3 12 2 4 3 2 8 12 2 6 14 2 9 16 2 13 1 2 15 15 2 9 16 2 10 10 2 5 4 2 7 17 18 26 2 16 4 2 10 15 1 7 1 13 1 11 1 11 2 15 10 1 14 1 5 1 8 2 9 3 2 2 9 2 4 12 1 13 1 1 1 1 1 17 1 5 2 16 6 1 7 1 8 2 12 6 1 17 2 18 3 1 14 2 2 18 18 23 2 16 16 2 18...
output:
19 9 5 11 5 10 9 18 10 1 18 1 11 2 1 6 1 19 6 2 19 13 2 16 2 13 16 3 13 14 3 13 14 7 13 12 7 13 12 21 15 16 9 18 3 20 10 21 5 6 4 14 8 25 17 23 11 8 24 8 12 11 26 24 12 26 19 12 22 12 13 22 1 13 1 19 2 1 7 2 1 7 14 10 12 6 13 16 23 11 16 15 16 2 11 4 15 19 2 20 4 7 19 7 20 14 7 17 14 7 17 -1 16 5 16...
result:
ok 5263 cases passed. max #moves/#balls = 1.388888889
Test #20:
score: 0
Accepted
time: 29ms
memory: 7908kb
input:
19 25 2 8 13 0 1 16 1 5 2 18 13 2 4 7 0 2 17 1 2 12 16 2 12 4 2 19 15 2 1 8 1 3 1 7 2 6 2 2 2 9 2 18 14 1 11 2 10 10 2 15 17 2 6 14 1 5 2 9 19 1 11 1 3 19 34 1 12 1 16 1 16 1 7 1 6 2 4 4 1 8 1 18 2 9 19 1 11 1 13 1 14 1 7 1 6 1 3 1 14 2 9 5 1 11 1 15 1 1 1 3 2 19 1 1 17 1 17 1 13 1 2 1 12 1 8 1 15 1...
output:
20 13 25 4 22 18 24 6 14 9 3 10 6 9 10 1 9 5 9 12 1 8 12 20 8 11 20 23 11 16 23 15 16 17 18 21 18 5 17 15 21 18 26 32 15 21 5 14 4 13 7 28 30 34 10 18 1 27 11 25 12 16 19 29 2 3 23 24 8 31 22 20 17 33 9 22 9 17 -1 21 24 25 5 7 17 23 14 19 18 21 2 9 11 27 1 11 4 11 15 1 20 4 6 2 8 2 6 15 8 20 13 8 22...
result:
ok 5000 cases passed. max #moves/#balls = 1.368421053
Test #21:
score: 0
Accepted
time: 29ms
memory: 5868kb
input:
20 36 1 3 1 19 1 18 1 19 1 2 1 4 1 17 2 5 6 1 1 1 12 1 14 1 20 1 11 1 13 1 7 1 15 1 16 1 3 1 1 1 16 1 11 1 4 1 8 1 15 2 9 5 1 8 1 13 1 7 1 12 1 2 2 10 10 1 17 1 18 1 14 1 20 2 6 9 20 27 2 7 13 2 6 10 0 2 11 8 2 11 2 0 1 17 2 1 1 1 15 1 19 1 19 1 14 2 4 5 1 14 2 12 8 2 7 6 2 2 12 2 3 20 2 18 20 2 3 4...
output:
20 9 19 5 30 1 18 6 22 15 28 23 26 13 21 10 29 14 27 11 34 16 24 17 20 7 32 3 33 2 4 12 35 8 12 25 8 36 25 12 36 22 12 14 9 22 26 27 7 25 10 11 4 10 15 10 17 15 5 17 4 5 13 4 24 4 20 13 18 7 19 7 18 20 19 24 1 19 23 19 2 23 16 2 1 16 21 12 16 21 28 7 13 14 24 2 10 20 22 9 17 18 26 4 11 8 29 23 30 1 ...
result:
ok 4761 cases passed. max #moves/#balls = 1.300000000
Test #22:
score: 0
Accepted
time: 16ms
memory: 5852kb
input:
70 79 2 13 14 2 49 46 1 43 2 27 27 2 5 5 2 63 50 2 63 15 2 61 25 2 17 39 2 44 26 2 15 45 2 65 2 2 64 6 2 2 28 2 55 60 2 13 68 1 40 2 30 30 1 62 2 41 60 2 16 25 1 69 1 62 2 28 23 2 46 49 2 26 57 1 35 2 66 66 2 10 69 2 33 55 1 10 2 54 9 1 32 2 11 12 1 40 1 7 1 29 2 33 54 2 12 11 2 22 1 1 29 2 6 64 2 2...
output:
79 36 45 37 41 33 75 27 62 17 35 3 47 44 50 19 23 29 22 29 31 40 19 52 19 63 40 9 63 26 44 60 44 52 60 10 26 72 10 9 72 6 9 73 9 11 52 74 52 7 11 6 7 76 74 51 76 48 51 56 48 56 73 32 6 61 6 38 32 78 61 68 29 79 29 78 79 15 78 20 78 20 68 30 15 30 38 1 3 65 3 16 65 1 16 55 30 67 30 54 67 8 56 21 56 2...
result:
ok 1000 cases passed. max #moves/#balls = 1.500000000
Test #23:
score: 0
Accepted
time: 11ms
memory: 5912kb
input:
89 125 2 6 86 1 11 1 43 1 77 1 27 2 72 88 1 52 2 26 75 1 77 2 89 86 1 60 1 18 2 20 20 1 25 2 57 75 1 3 1 55 2 38 19 2 76 2 2 22 24 1 3 2 61 61 2 39 59 2 42 74 1 56 2 71 71 1 68 2 79 87 2 81 67 1 25 2 66 21 1 37 1 70 2 40 83 1 60 1 48 1 52 2 22 24 2 62 62 1 84 2 41 23 1 69 2 32 26 1 36 1 15 2 88 72 1...
output:
88 16 21 48 92 54 93 2 105 79 88 59 96 57 107 45 114 85 91 12 108 14 30 5 47 73 116 51 78 56 112 44 87 32 117 3 75 110 113 82 118 61 98 36 94 62 76 7 37 17 123 25 90 95 109 11 35 27 122 42 52 33 115 83 119 4 9 40 64 63 106 19 40 67 40 70 19 63 70 34 67 34 77 49 34 102 34 80 102 49 80 74 49 86 49 23 ...
result:
ok 100 cases passed. max #moves/#balls = 1.169811321
Test #24:
score: 0
Accepted
time: 80ms
memory: 10580kb
input:
199990 199994 2 112787 58235 2 74630 28941 2 167642 28933 2 133872 119903 2 134119 187247 2 12074 126849 2 172463 191232 2 69306 129651 2 85342 121061 2 31874 148765 2 6567 39825 2 70847 178127 2 161417 173942 2 60884 49005 2 10700 112396 2 134185 131889 2 62930 176558 2 153356 48329 2 88968 136672 ...
output:
249866 45681 123950 47930 39403 52624 103430 29499 45681 33532 199994 149868 199994 55718 149868 55718 174021 40140 55718 154492 55718 3409 40140 98071 154492 33532 98071 127577 3409 146781 33532 183763 33532 127577 146781 177569 183763 39870 177569 128051 39870 40416 128051 47653 40416 24457 47653 ...
result:
ok 1 cases passed. max #moves/#balls = 1.249392470
Test #25:
score: 0
Accepted
time: 85ms
memory: 10560kb
input:
199900 199939 2 159852 65847 2 26090 50275 2 87513 124862 2 86896 171149 2 108960 21092 2 60944 176432 2 64408 168417 2 110938 48609 2 30886 178149 2 180183 52005 2 185615 173446 2 91034 36919 2 121714 75547 2 97679 89549 2 161524 190571 2 129781 26065 2 726 162459 2 28052 166745 2 193665 65435 2 45...
output:
249613 106581 195508 83100 170999 118999 98362 87499 466 13675 161933 60082 64253 25955 165035 141785 86599 124306 101796 193462 112079 113064 98870 111161 180271 70518 20388 177189 95960 96222 102294 51089 145236 78606 55030 42342 50137 130367 94233 87678 119173 197876 195998 141132 188272 167502 5...
result:
ok 1 cases passed. max #moves/#balls = 1.248689345
Test #26:
score: 0
Accepted
time: 74ms
memory: 10660kb
input:
199000 199158 2 87128 180318 2 51427 22755 2 151883 144846 2 86404 42933 2 86031 56171 2 97601 190366 2 100929 91717 2 10606 53797 2 151688 90226 2 65599 83910 2 159670 153323 2 98395 126956 2 104190 188119 2 134860 5110 2 82527 59574 2 185228 58544 2 131591 9348 2 88390 99580 2 79913 120984 2 12854...
output:
248620 159826 170232 460 63968 824 116779 144747 178190 65806 96668 127166 172896 64102 145895 184853 35084 41063 63660 46344 122341 96981 145392 110701 113358 191723 110773 103047 42388 93580 153682 132545 16452 108644 192770 83363 51763 110485 176389 150694 86082 5748 32464 28323 198599 143694 167...
result:
ok 1 cases passed. max #moves/#balls = 1.249346734
Test #27:
score: 0
Accepted
time: 72ms
memory: 10528kb
input:
190000 195490 2 57925 137657 2 115225 31941 2 113825 126389 2 86640 44883 2 54487 34585 2 118366 61471 2 120619 96922 1 140665 2 42131 138488 2 115971 83797 2 79814 139047 2 182772 4122 2 134485 135722 2 83056 53620 2 4840 71513 2 58767 175090 2 55378 47553 2 158331 65564 2 2231 167672 2 45248 44008...
output:
234894 115305 173688 59173 162528 154636 191315 2345 134194 35960 172070 81231 144419 41297 67516 45199 54669 177867 185539 5835 134098 26450 186598 4023 39925 31497 116217 131028 153733 142872 179043 55368 167022 24444 172578 21069 131898 13697 86705 54857 57867 104032 105478 30688 82920 107437 156...
result:
ok 1 cases passed. max #moves/#balls = 1.236284211
Test #28:
score: 0
Accepted
time: 40ms
memory: 10964kb
input:
100000 150784 1 11363 2 48695 10015 1 45261 0 0 2 59469 34868 2 37754 54971 2 1159 2258 2 36656 7427 1 86418 0 2 58664 20429 1 53392 1 61881 2 17499 14399 1 31182 1 7141 0 2 58765 17577 1 21750 2 55759 24096 0 0 2 68221 45178 1 34307 1 952 0 1 37862 1 31349 2 79909 53730 2 61993 40470 0 1 8272 2 824...
output:
111036 4709 37327 12514 126560 40604 80635 20806 112227 25767 46609 24650 46902 80991 141613 49054 140135 14362 130535 22358 33893 9919 89093 102297 136505 126469 141173 78525 134207 125222 149492 7809 66841 2232 8426 27574 133665 67047 124348 52285 116414 60881 146565 144720 147826 49620 138835 297...
result:
ok 1 cases passed. max #moves/#balls = 1.110360000
Test #29:
score: 0
Accepted
time: 69ms
memory: 10788kb
input:
199998 200000 2 197320 165241 2 136684 67821 2 38136 196111 2 36675 168634 2 193814 85383 2 188893 178378 2 107377 34791 2 77322 157440 2 51337 91683 2 141729 123337 2 88834 166216 2 172041 99918 2 81678 190214 2 145905 79139 2 184733 143722 2 20662 175460 2 73374 152647 2 111949 12058 2 7347 64349 ...
output:
250095 15752 200000 193137 200000 38423 15752 18069 38423 70312 18069 48704 199999 171485 199999 48704 193137 181432 171485 21389 48704 86073 48704 88923 21389 52175 88923 120332 52175 5957 120332 8804 5957 80803 8804 185992 80803 166780 185992 153647 166780 153647 181432 42056 153647 117020 153647 ...
result:
ok 1 cases passed. max #moves/#balls = 1.250487505