QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#418808 | #2830. Data Structure | dieselhuang | AC ✓ | 101ms | 13540kb | C++14 | 2.7kb | 2024-05-23 15:52:56 | 2024-05-23 15:52:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int n, m, X, Y, tp, cnt, k[200010], a[200010][2], pos[200010][2], stk[400010], ans[300010][2];
bool bk[200010];
void chg(int x, int y){
cnt++; ans[cnt][0] = x; ans[cnt][1] = y;
if(X == y){ X = Y; Y = 0; }
else if(Y == y) Y = 0;
int i = a[x][--k[x]];
if(pos[i][0] == x) pos[i][0] = y;
else pos[i][1] = y;
a[y][k[y]++] = i;
if(k[x] > 0) stk[++tp] = a[x][k[x] - 1];
else if(X == 0) X = x;
else if(Y == 0) Y = x;
}
void upd(){
int i, x, y;
while(tp > 0){
i = stk[tp--]; x = pos[i][0]; y = pos[i][1];
if(x == y || i != a[x][k[x] - 1] || i != a[y][k[y] - 1]) continue;
if(k[x] == 1) chg(y, x);
else if(k[y] == 1) chg(x, y);
}
}
void dfs1(int u, int fa){
int x = pos[u][0] + pos[u][1] - fa;
bool fl = (a[fa][k[fa] - 1] == u && a[x][k[x] - 1] == u);
if(k[x] > 1) dfs1(a[x][0] + a[x][1] - u, x);
if(fl){
int tmp = X;
chg(fa, tmp); chg(x, tmp); upd();
}
}
void dfs2(int u, int fa, int rt, int &p){
int x = pos[u][0] + pos[u][1] - fa;
if(a[fa][1] == u && a[x][1] == u){
if(p == 0) p = u;
else p = -1;
}
if(x != rt) dfs2(a[x][0] + a[x][1] - u, x, rt, p);
}
void dfs3(int u, int fa, int rt){
bk[fa] = true;
int x = pos[u][0] + pos[u][1] - fa;
if(x != rt) dfs3(a[x][0] + a[x][1] - u, x, rt);
}
void dfs4(int u, int fa, int rt){
int x = pos[u][0] + pos[u][1] - fa;
bool fl = (a[fa][1] == u && a[x][1] == u);
if(x != rt) dfs4(a[x][0] + a[x][1] - u, x, rt);
if(fl){
int tmp = X;
chg(fa, tmp); chg(x, tmp); upd();
}
}
void solve(){
X = 0; Y = 0; tp = 0; cnt = 0;
int i, j, tmp;
for(i = 1; i <= n; i++) pos[i][0] = 0;
for(i = 1; i <= m; i++){
scanf("%d", &k[i]);
for(j = 0; j < k[i]; j++){
scanf("%d", &a[i][j]);
if(pos[a[i][j]][0] == 0) pos[a[i][j]][0] = i;
else pos[a[i][j]][1] = i;
}
if(k[i] > 0) stk[++tp] = a[i][k[i] - 1];
else if(X == 0) X = i;
else if(Y == 0) Y = i;
bk[i] = false;
}
upd();
if(X != 0){
for(i = 1; i <= m; i++){
if(k[i] == 1) dfs1(a[i][k[i] - 1], i);
}
for(i = 1; i <= m; i++){
if(k[i] == 2 && !bk[i] && a[i][0] != a[i][1]){
j = 0; dfs2(a[i][0], i, i, j);
if(j == 0){
chg(i, X); upd();
}else if(j > 0){
tmp = X; chg(pos[j][0], tmp); chg(pos[j][1], tmp); upd();
}else dfs3(a[i][0], i, i);
}
}
if(Y != 0){
for(i = 1; i <= m; i++){
if(k[i] == 2 && bk[i] && a[i][0] != a[i][1]){
dfs4(a[i][0], i, i);
}
}
}
}
for(i = 1; i <= n; i++){
if(pos[i][0] != pos[i][1]){ printf("-1\n"); return; }
}
printf("%d\n", cnt);
for(i = 1; i <= cnt; i++) printf("%d %d\n", ans[i][0], ans[i][1]);
}
int main()
{
while(~scanf("%d%d", &n, &m)){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9984kb
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 2 1 0 -1
result:
ok 3 cases passed. max #moves/#balls = 1.500000000
Test #2:
score: 0
Accepted
time: 1ms
memory: 10080kb
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 2 1 1 3 1 1 2 1 0 0 0
result:
ok 6 cases passed. max #moves/#balls = 1.000000000
Test #3:
score: 0
Accepted
time: 0ms
memory: 8036kb
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 4 1 3 2 2 5 2 4 1 2 6 5 4 2 2 4 1 3 2 2 5 1 4 3 2 6 1 5 3 2 4 1 3 2 2 5 2 4 3 2 6 1 4 3 2 1 2 3 1 2 1 2 4 1 2 4 3 4 1 2 2 1 3 2 2 2 1 3 2 2 1 3 4 1 -1 3 2 1 3 1 3 2 3 2 1 4 1 4 2 -1 3 1 3 2 1 2 3 3 1 3 2 1 2 3 1 3 2 1 4 3 1 4 1 0 0 0
result:
ok 27 cases passed. max #moves/#balls = 1.500000000
Test #4:
score: 0
Accepted
time: 0ms
memory: 9960kb
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 6 1 5 4 3 2 3 7 1 6 5 4 3 3 8 2 7 3 6 5 3 6 3 5 4 2 1 3 6 2 5 4 3 1 3 8 1 7 4 5 2 3 6 2 5 3 4 1 3 7 2 6 5 4 1 3 8 2 6 3 4 1 3 6 3 5 4 2 1 3 7 4 6 3 5 2 3 8 5 4 3 2 1 3 6 1 5 2 4 3 3 7 4 6 5 3 1 3 8 4 7 6 5 2 3 6 3 5 4 2 1 3 7 2 6 5 3 1 3 8 6 7 3 4 2 3 6 4 5 1 3 2 3 7 4 5 1 3 2 3 8 4 7 5 6 1 3 6 4 ...
result:
ok 180 cases passed. max #moves/#balls = 1.333333333
Test #5:
score: 0
Accepted
time: 0ms
memory: 10068kb
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 8 5 7 3 6 4 2 1 4 9 1 8 3 7 5 6 4 4 9 8 7 1 5 4 3 2 4 8 2 7 5 6 1 4 3 4 8 6 7 3 5 1 4 2 4 10 1 9 4 8 2 7 3 4 8 7 6 3 5 1 4 2 4 9 1 8 2 6 4 5 3 4 10 8 7 4 6 5 3 2 4 8 2 7 4 6 5 3 1 4 9 2 7 1 6 5 4 3 4 10 2 9 1 8 3 5 4 4 8 4 7 6 5 2 3 1 4 9 4 8 3 7 2 5 1 4 9 2 8 1 7 5 6 3 4 8 2 7 6 5 1 4 3 4 9 3 8 2...
result:
ok 1575 cases passed. max #moves/#balls = 1.500000000
Test #6:
score: 0
Accepted
time: 22ms
memory: 10016kb
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 10 7 9 1 8 5 6 3 4 2 5 11 9 10 2 8 5 6 4 3 1 5 12 3 11 7 10 4 8 6 5 1 5 10 1 9 5 8 2 7 6 4 3 5 11 2 10 5 8 7 6 1 4 3 5 12 1 10 5 9 2 8 6 7 3 5 10 3 9 8 7 4 6 2 5 1 5 11 3 9 8 7 5 6 1 4 2 5 11 10 9 8 7 1 5 4 3 2 5 10 8 9 2 7 6 5 4 3 1 5 11 1 9 8 7 6 5 4 3 2 5 11 4 10 3 9 8 7 1 6 2 5 10 1 9 3 8 7 6 ...
result:
ok 17010 cases passed. max #moves/#balls = 1.400000000
Test #7:
score: 0
Accepted
time: 22ms
memory: 9988kb
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 11 5 10 8 10 3 9 2 7 4 6 1 5 5 4 5 1 7 6 9 6 9 7 -1 8 7 3 1 6 4 1 4 6 5 7 8 7 2 8 5 2 7 9 4 8 1 7 9 5 9 5 3 6 7 6 2 5 2 7 5 2 3 5 4 1 4 3 5 7 1 8 7 6 3 2 6 8 2 5 11 8 10 3 9 1 7 5 6 2 6 1 6 5 1 3 8 4 8 2 4 3 2 -1 6 12 7 11 1 10 5 9 4 8 6 3 2 3 7 6 5 7 5 3 8 7 2 1 2 9 1 4 7 4 3 5 6 8 6 8 5 6 14 2 1...
result:
ok 14285 cases passed. max #moves/#balls = 1.500000000
Test #8:
score: 0
Accepted
time: 23ms
memory: 10016kb
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 9 2 1 8 4 8 4 1 7 12 8 11 1 7 10 9 4 5 6 7 5 3 2 7 15 3 14 9 13 8 12 6 11 7 5 2 4 1 -1 7 12 2 10 7 9 6 8 4 1 5 3 1 11 3 7 14 3 13 10 12 4 11 9 8 5 1 7 6 1 7 6 1 3 2 10 2 8 10 4 8 7 3 7 4 7 12 5 2 11 6 2 6 3 10 7 9 8 4 1 7 5 11 10 2 6 4 3 1 7 1 9 7 5 3 7 9 5 7 2 4 1 6 4 8 9 10 9 10 8 7 14 12 14 7 1...
result:
ok 12500 cases passed. max #moves/#balls = 1.428571429
Test #9:
score: 0
Accepted
time: 26ms
memory: 7948kb
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 16 14 15 9 11 1 10 5 8 4 6 3 9 13 7 12 9 12 2 11 1 10 4 8 3 5 13 6 13 6 5 -1 8 16 1 15 12 14 11 13 8 10 2 9 3 7 4 6 5 9 15 7 14 6 12 8 10 5 9 1 11 3 13 3 13 4 11 2 9 8 1 9 1 2 8 9 2 3 9 7 9 5 7 4 3 5 4 7 6 2 1 9 8 9 5 8 10 1 4 10 5 4 8 16 4 15 14 13 5 12 10 11 2 9 7 8 3 6 1 10 8 5 1 9 6 9 11 1 2 1...
result:
ok 11111 cases passed. max #moves/#balls = 1.500000000
Test #10:
score: 0
Accepted
time: 23ms
memory: 10084kb
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 12 5 4 11 4 1 9 7 8 6 2 12 3 2 3 12 10 4 13 4 13 10 11 12 11 5 1 8 7 2 7 3 2 6 3 4 10 9 10 13 9 13 8 6 4 9 18 4 17 1 16 13 15 9 14 11 12 8 10 7 6 5 3 2 8 12 4 7 11 6 7 8 6 2 1 9 1 5 9 5 2 9 17 9 16 15 14 5 13 1 6 12 11 3 10 4 2 7 6 2 13 1 3 10 3 10 1 2 4 8 2 8 4 5 10 6 10 9 6 9 5 7 8 11 7 11 8 8 ...
result:
ok 10000 cases passed. max #moves/#balls = 1.444444444
Test #11:
score: 0
Accepted
time: 23ms
memory: 10024kb
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 19 16 18 4 17 3 15 6 14 2 13 10 11 9 8 7 5 1 7 19 1 16 2 15 4 13 5 12 9 11 7 10 6 -1 10 18 8 17 7 16 13 15 10 14 9 12 2 11 6 5 4 19 5 3 1 11 19 4 17 3 16 15 14 8 12 10 9 1 5 6 13 5 7 2 18 7 18 2 7 19 17 18 12 16 8 14 10 13 6 9 5 3 1 10 18 11 17 10 16 9 15 2 14 7 3 13 5 3 5 1 12 8 6 4 10 3 19 4 3 1...
result:
ok 9090 cases passed. max #moves/#balls = 1.500000000
Test #12:
score: 0
Accepted
time: 28ms
memory: 8016kb
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 15 12 15 11 10 9 6 3 5 4 8 4 7 8 13 7 13 5 13 15 12 13 2 9 6 8 7 5 4 3 15 16 15 16 11 17 3 14 13 1 13 17 1 14 10 10 21 3 20 16 18 10 17 6 15 13 14 2 12 4 11 5 9 7 8 1 11 15 3 12 11 8 12 15 8 10 1 9 2 13 6 14 6 7 14 5 7 13 5 10 19 2 18 14 17 12 16 8 15 4 13 9 5 11 16 5 10 7 6 3 11 7 10 12 7 1 12 4 ...
result:
ok 8333 cases passed. max #moves/#balls = 1.363636364
Test #13:
score: 0
Accepted
time: 24ms
memory: 10000kb
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 25 24 23 8 22 5 21 7 20 3 19 13 18 9 17 4 16 2 14 11 12 1 10 6 11 18 17 6 16 4 6 15 1 13 12 11 2 9 7 9 4 10 5 14 10 14 5 9 1 7 13 1 12 13 12 7 5 11 10 11 3 10 6 3 6 5 10 14 5 8 5 3 8 1 3 7 13 12 13 4 12 6 4 14 6 7 1 12 25 16 24 11 22 8 21 12 20 4 19 5 18 15 17 9 14 7 13 3 10 1 6 2 11 12 2 5 4 8 9...
result:
ok 7692 cases passed. max #moves/#balls = 1.416666667
Test #14:
score: 0
Accepted
time: 36ms
memory: 10088kb
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 13 8 11 9 7 13 10 13 6 7 10 6 12 18 3 15 6 13 12 11 8 7 5 4 2 9 16 21 9 21 16 14 20 19 20 19 14 11 24 6 23 13 22 8 20 15 19 2 18 5 17 3 16 10 14 1 12 4 9 7 12 20 13 17 3 16 4 15 8 14 2 11 1 10 6 9 7 10 9 5 20 19 20 19 5 12 27 1 26 12 25 2 23 5 22 21 20 4 19 11 18 9 17 7 16 10 14 8 6 3 13 26 23 25 ...
result:
ok 7142 cases passed. max #moves/#balls = 1.384615385
Test #15:
score: 0
Accepted
time: 24ms
memory: 9940kb
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 24 21 8 24 10 8 13 10 23 19 22 14 20 12 18 4 17 3 11 1 9 5 13 9 7 2 13 27 24 26 9 25 1 23 12 22 17 20 16 19 8 18 7 15 11 14 6 13 2 10 5 4 3 12 22 19 21 4 20 14 17 1 15 3 8 13 11 8 6 5 2 18 7 18 10 2 10 7 13 25 16 21 6 20 8 19 2 18 11 17 14 15 4 12 7 10 9 3 1 13 24 23 24 23 13 14 29 22 28 3 27 1 2...
result:
ok 6666 cases passed. max #moves/#balls = 1.357142857
Test #16:
score: 0
Accepted
time: 32ms
memory: 10080kb
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 21 4 17 11 10 15 9 10 6 5 2 3 14 2 13 1 12 1 22 12 13 9 8 7 19 8 19 7 13 24 15 13 24 19 13 23 18 22 6 20 1 17 2 14 17 3 14 19 3 16 10 12 11 8 4 12 24 23 22 6 8 18 8 5 16 15 14 9 13 10 12 7 3 2 17 1 19 1 19 17 15 17 6 7 3 13 3 13 7 14 17 2 17 12 14 15 13 11 13 12 11 16 12 10 12 15 10 5 16 5 2 16 2...
result:
ok 6250 cases passed. max #moves/#balls = 1.400000000
Test #17:
score: 0
Accepted
time: 24ms
memory: 10128kb
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 20 8 15 6 7 5 9 7 4 2 22 3 21 3 21 14 22 1 18 16 23 16 23 19 12 18 12 9 17 29 11 28 18 27 24 26 21 25 6 23 9 23 17 22 4 19 14 15 12 13 7 13 2 10 5 8 3 16 1 20 16 20 1 16 28 6 27 16 26 19 25 7 24 3 24 15 23 12 22 9 21 10 20 13 17 4 14 2 11 1 5 28 18 28 18 5 15 23 7 21 15 19 10 18 12 14 8 13 1 6 3 ...
result:
ok 5882 cases passed. max #moves/#balls = 1.375000000
Test #18:
score: 0
Accepted
time: 21ms
memory: 8080kb
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 33 6 32 28 31 23 30 8 29 21 27 26 25 13 22 16 20 17 19 3 18 9 15 1 14 10 12 7 11 4 2 5 24 5 24 2 16 23 11 20 12 19 3 18 5 18 14 15 16 8 15 10 1 2 23 22 23 22 8 4 2 6 20 9 6 17 9 17 20 15 17 6 2 7 18 2 10 18 10 7 4 8 13 8 13 4 11 10 20 10 5 11 16 5 14 16 9 14 20 9 18 34 18 33 23 32 3 31 13 29 15 2...
result:
ok 5555 cases passed. max #moves/#balls = 1.352941176
Test #19:
score: 0
Accepted
time: 30ms
memory: 8088kb
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 11 1 2 11 6 11 19 6 19 2 3 19 14 3 14 19 7 14 12 7 12 14 13 12 16 12 16 13 21 25 8 23 17 21 10 20 3 18 9 16 15 14 4 6 5 19 25 22 25 13 22 1 13 19 1 2 23 7 2 7 23 11 19 24 19 26 24 12 11 26 12 14 23 16 13 6 12 10 11 18 15 18 4 15 20 4 2 11 19 2 7 19 20 7 14 21 17 14 17 21 ...
result:
ok 5263 cases passed. max #moves/#balls = 1.388888889
Test #20:
score: 0
Accepted
time: 29ms
memory: 8040kb
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 25 13 24 18 22 4 6 14 10 6 9 3 10 9 5 2 1 2 12 1 8 12 20 8 11 20 23 11 16 23 15 16 21 7 17 7 17 5 21 15 18 34 30 17 33 32 26 31 8 29 19 28 7 27 1 25 11 24 23 22 20 9 22 17 9 21 15 18 10 16 12 14 5 13 4 3 2 -1 21 27 11 25 24 23 17 21 18 19 14 9 2 7 5 12 3 16 12 16 3 13 27 22 27 22 13 4 16 1 16 15 ...
result:
ok 5000 cases passed. max #moves/#balls = 1.368421053
Test #21:
score: 0
Accepted
time: 22ms
memory: 10128kb
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 35 12 34 11 33 3 32 7 30 5 29 10 28 15 27 14 26 23 24 16 22 6 21 13 20 17 19 9 18 1 4 2 8 35 25 8 36 25 36 35 22 27 26 25 7 22 9 14 12 11 10 1 3 23 3 2 23 16 2 16 1 4 6 15 6 17 15 5 17 5 4 24 16 13 16 20 13 18 5 19 5 24 19 20 18 21 30 23 29 8 28 21 26 18 24 14 22 20 17 9 16 12 13 7 11 4 10 2 1 30...
result:
ok 4761 cases passed. max #moves/#balls = 1.300000000
Test #22:
score: 0
Accepted
time: 15ms
memory: 7980kb
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 75 33 62 27 50 44 47 3 45 36 41 37 35 17 29 22 31 29 23 19 1 75 65 75 16 65 16 1 2 62 25 2 25 62 12 16 71 12 24 71 14 24 14 16 13 25 42 13 42 25 34 14 39 34 39 14 46 42 66 46 66 42 53 39 57 53 70 57 70 39 58 66 77 66 77 58 73 70 6 70 11 77 74 77 76 74 51 76 48 51 56 48 73 56 7 11 7 6 21 73 8 73 6...
result:
ok 1000 cases passed. max #moves/#balls = 1.500000000
Test #23:
score: 0
Accepted
time: 11ms
memory: 8096kb
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 123 17 122 27 119 83 118 82 117 32 116 73 115 33 114 45 113 110 112 56 109 95 108 12 107 57 63 106 105 2 98 61 96 59 94 36 93 54 92 48 91 85 90 25 88 79 87 44 78 51 76 62 75 3 64 40 52 42 47 5 37 7 35 11 30 14 21 16 9 4 19 81 67 81 34 67 77 34 70 19 70 63 6 123 46 6 46 123 8 77 15 77 89 15 43 8 8...
result:
ok 100 cases passed. max #moves/#balls = 1.169811321
Test #24:
score: 0
Accepted
time: 86ms
memory: 12840kb
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 29499 45681 52624 103430 47930 39403 33532 199993 149868 199993 55718 149868 174021 55718 40140 199994 154492 199994 98071 154492 98071 33532 3409 40140 127577 3409 183763 174021 146781 174021 146781 127577 177569 183763 39870 177569 128051 39870 40416 128051 47653 40416 24457 47...
result:
ok 1 cases passed. max #moves/#balls = 1.249392470
Test #25:
score: 0
Accepted
time: 80ms
memory: 11980kb
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 197876 195998 106581 195508 61879 106581 193688 130694 193462 112079 79103 193462 142645 79103 137649 142645 141132 188272 186238 148645 110210 186238 144467 110210 172814 144467 184780 156194 36392 181613 11595 36392 111161 180271 177189 95960 83100 170999 146264 83100 109914 146264 73827 17...
result:
ok 1 cases passed. max #moves/#balls = 1.248689345
Test #26:
score: 0
Accepted
time: 85ms
memory: 11900kb
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 177708 198873 2295 177708 190108 2295 28323 198599 162531 28323 130923 197526 108690 130923 194040 96305 186424 193560 193496 103084 108644 192770 52653 108644 191949 77512 191723 110773 64324 191723 186152 40397 184853 35084 184348 40546 55779 184348 9660 55779 39136 9660 57803 183718 159981...
result:
ok 1 cases passed. max #moves/#balls = 1.249346734
Test #27:
score: 0
Accepted
time: 73ms
memory: 11936kb
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 57287 195481 50352 57287 113863 195478 195463 37750 195422 112777 43842 195416 52331 195344 123184 52331 84121 123184 157137 195326 40458 195298 195288 122237 195273 45436 195252 83076 50768 195245 127165 50768 5090 195241 7113 5090 195233 176847 154240 195153 195151 63028 74767 195134 130367...
result:
ok 1 cases passed. max #moves/#balls = 1.236284211
Test #28:
score: 0
Accepted
time: 38ms
memory: 11584kb
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 142726 150781 5647 142726 115157 5647 3218 115157 150780 113716 29540 150779 25421 150773 98471 25421 150770 140176 150767 53323 5969 150766 150765 127582 150765 45925 150758 112446 67697 150755 121922 67697 127998 150753 127998 238 150751 71134 81770 150750 81770 60056 150745 39859 150743 14...
result:
ok 1 cases passed. max #moves/#balls = 1.110360000
Test #29:
score: 0
Accepted
time: 101ms
memory: 13540kb
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 53982 199999 138669 199999 35536 138669 1 35536 19591 1 156892 200000 26080 200000 22878 26080 53982 22878 139880 156892 5236 139880 141273 53982 8108 53982 45569 8108 45569 5236 154646 45569 37924 45569 147006 37924 147006 141273 28742 154646 143141 147006 94441 147006 94441 28742 29668 1431...
result:
ok 1 cases passed. max #moves/#balls = 1.250487505