QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#223929 | #2830. Data Structure | ucup-team1004 | AC ✓ | 122ms | 27188kb | C++14 | 2.7kb | 2023-10-22 21:05:49 | 2023-10-22 21:05:49 |
Judging History
answer
#include <cstdio>
#include <vector>
using namespace std;
int n, m;
vector<vector<int>> s;
vector<vector<pair<int, int>>> pos;
vector<pair<int, int>> ans;
vector<int> empty;
void move(int i, int j) {
int c = s[i].back();
s[j].push_back(c);
s[i].pop_back();
if (s[i].size() == 0) {
empty.push_back(i);
}
int id = i == pos[c][1].second ? 1 : 0;
pos[c][id].first = s[j].size() - 1;
pos[c][id].second = j;
ans.push_back(make_pair(i + 1, j + 1));
}
bool solve_chain(int start) {
int ci = start, ch = 0;
while (true) {
int cc = s[ci][ch], id = ci == pos[cc][1].second ? 1 : 0,
chp = pos[cc][1 - id].first, cip = pos[cc][1 - id].second;
if (s[cip].size() == 1) {
if (s[ci].size() == 1) {
move(ci, cip);
return true;
} else {
return solve_chain(cip);
}
} else {
if (s[ci].size() == 1 && chp == 1) {
move(cip, ci);
}
if (ch == 0 || chp == 0) {
ci = cip;
ch = 1 - chp;
} else {
if (empty.size() == 0) {
return false;
} else {
int tmp = empty.back();
empty.pop_back();
move(ci, tmp);
solve_chain(ci);
return solve_chain(tmp);
}
}
}
}
}
int main() {
while (scanf("%d%d", &n, &m) != -1) {
s.resize(m);
for (int i = 0; i < m; ++i) {
s[i].clear();
}
pos.resize(n);
for (int i = 0; i < n; ++i) {
pos[i].clear();
}
empty.clear();
ans.clear();
for (int i = 0; i < m; ++i) {
int sz;
scanf("%d", &sz);
if (sz == 0) {
empty.push_back(i);
}
for (int j = 0; j < sz; ++j) {
int c;
scanf("%d", &c);
--c;
s[i].push_back(c);
pos[c].push_back(make_pair(j, i));
}
}
for (int r = 0; r < 2; ++r) {
for (int i = 0; i < m; ++i) {
if (s[i].size() == 1) {
solve_chain(i);
}
}
}
bool valid = true;
for (int r = 0; r < 2; ++r) {
for (int i = 0; i < n; ++i) {
if ((r == 0 && pos[i][0].first == 1 && pos[i][1].first == 1) ||
(r == 1 && pos[i][0].second != pos[i][1].second)) {
if (empty.size() > 0) {
int ti = pos[i][0].second, tmp = empty.back();
empty.pop_back();
move(ti, tmp);
solve_chain(ti);
} else {
valid = false;
}
}
}
}
if (!valid) {
printf("-1\n");
} else {
printf("%d\n", (int)ans.size());
for (int i = 0; i < (int)ans.size(); ++i) {
printf("%d %d\n", ans[i].first, ans[i].second);
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3924kb
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: 0ms
memory: 3860kb
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: 0ms
memory: 3916kb
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 1 4 2 3 2 1 5 3 4 2 1 6 3 5 2 1 4 2 3 2 2 5 3 4 2 1 6 3 4 2 1 2 1 3 2 1 2 1 4 2 4 3 4 1 2 2 1 2 3 2 2 1 2 3 2 1 3 1 4 -1 3 2 1 3 1 3 2 3 2 3 4 3 4 2 -1 3 1 3 2 1 2 3 3 1 4 2 1 2 4 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: 3792kb
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 1 7 3 4 5 6 3 2 8 3 7 5 6 3 1 2 3 6 4 5 3 1 3 2 6 4 5 3 1 8 2 5 4 7 3 1 4 2 6 3 5 3 1 4 2 7 5 6 3 1 4 2 8 3 6 3 1 2 3 6 4 5 3 2 5 3 6 4 7 3 1 2 3 4 5 8 3 1 6 2 5 3 4 3 1 3 4 7 5 6 3 2 5 4 8 6 7 3 1 2 3 6 4 5 3 1 3 2 7 5 6 3 2 4 3 7 6 8 3 1 5 2 3 4 6 3 1 5 2 3 4 7 3 1 6 4 8 5 7 3 1 5 ...
result:
ok 180 cases passed. max #moves/#balls = 1.333333333
Test #5:
score: 0
Accepted
time: 2ms
memory: 3816kb
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 1 2 3 7 4 6 5 8 4 1 9 3 8 4 6 5 7 4 1 7 2 3 4 5 8 9 4 1 6 2 8 3 4 5 7 4 1 5 2 4 3 7 6 8 4 1 10 2 8 3 7 4 9 4 1 5 2 4 3 6 7 8 4 1 9 2 8 3 5 4 6 4 2 3 4 7 5 6 8 10 4 1 3 2 8 4 7 5 6 4 1 7 2 9 3 4 5 6 4 1 9 2 10 3 8 4 5 4 1 3 2 5 4 8 6 7 4 1 5 2 7 3 8 4 9 4 1 8 2 9 3 6 5 7 4 1 5 2 8 3 4 6 7 4 1 5 2 8...
result:
ok 1575 cases passed. max #moves/#balls = 1.500000000
Test #6:
score: 0
Accepted
time: 27ms
memory: 3912kb
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 2 4 3 6 5 8 7 10 5 1 3 2 10 4 6 5 8 9 11 5 1 5 3 12 4 10 6 8 7 11 5 1 10 2 8 3 4 5 9 6 7 5 1 6 2 11 3 4 5 10 7 8 5 1 12 2 9 3 7 5 10 6 8 5 1 5 2 6 3 10 4 7 8 9 5 1 6 2 4 3 11 5 7 8 9 5 1 7 2 3 4 5 8 9 10 11 5 1 3 2 9 4 5 6 7 8 10 5 1 11 2 3 4 5 6 7 8 9 5 1 7 2 6 3 10 4 11 8 9 5 1 10 2 6 3 9 4 ...
result:
ok 17010 cases passed. max #moves/#balls = 1.400000000
Test #7:
score: 0
Accepted
time: 26ms
memory: 3936kb
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 1 6 2 9 10 8 10 3 4 7 5 11 5 5 4 5 1 7 5 9 5 9 7 -1 8 3 7 5 3 8 3 2 8 2 5 1 2 4 1 4 2 7 1 8 7 1 6 7 6 2 5 1 5 3 4 9 5 4 1 2 7 5 2 3 5 3 4 5 7 1 8 7 6 3 2 6 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 1 11 2 3 4 9 5 10 6 8 7 12 3 7 6 5 7 5 3 8 7 6 4 7 4 3 1 6 1 9 5 1 8 1 8 5 6 1 3 2 ...
result:
ok 14285 cases passed. max #moves/#balls = 1.500000000
Test #8:
score: 0
Accepted
time: 26ms
memory: 3924kb
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 4 1 7 1 11 2 3 4 9 5 6 7 10 7 5 8 12 7 1 4 2 5 3 15 6 12 7 11 8 13 9 14 -1 7 2 12 4 8 1 5 3 1 3 11 6 9 7 10 7 3 14 4 12 5 8 1 7 1 6 9 11 10 13 7 1 6 3 1 7 3 10 1 8 10 4 8 4 7 7 1 4 2 11 6 2 6 3 5 12 7 10 8 9 7 2 10 4 6 7 4 7 9 3 4 5 11 5 3 7 4 1 4 6 2 7 5 9 8 5 10 5 10 8 7 1 13 2 9 3 8...
result:
ok 12500 cases passed. max #moves/#balls = 1.428571429
Test #9:
score: 0
Accepted
time: 26ms
memory: 3856kb
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 1 11 3 6 4 8 5 10 9 15 14 16 9 1 11 12 9 12 2 3 8 4 10 7 13 5 7 6 7 6 5 -1 8 1 16 2 10 3 9 4 7 5 6 8 13 11 14 12 15 9 1 9 11 1 11 2 13 1 13 4 5 10 6 14 7 15 8 12 9 8 1 2 8 9 1 9 2 3 9 4 3 7 9 5 7 5 4 7 2 6 1 2 10 1 4 10 8 2 5 8 5 4 8 1 6 2 11 3 8 4 16 5 13 7 9 10 12 14 15 10 5 8 3 5 4 3 7 5 7 4 1 ...
result:
ok 11111 cases passed. max #moves/#balls = 1.500000000
Test #10:
score: 0
Accepted
time: 27ms
memory: 3936kb
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 4 11 4 1 5 12 6 8 7 9 10 7 13 7 13 10 2 13 3 2 3 13 11 1 5 11 12 4 11 2 1 3 2 6 3 6 4 8 1 9 11 13 9 13 8 9 1 17 2 3 4 18 5 6 7 10 8 12 9 15 11 14 13 16 8 4 12 7 11 6 7 6 8 2 6 9 6 5 9 5 2 9 1 13 3 11 4 10 5 14 2 7 6 12 6 2 9 17 15 16 13 1 4 10 4 10 1 5 10 6 10 9 6 9 5 7 9 11 7 11 9 2 11 8 2 8 11 ...
result:
ok 10000 cases passed. max #moves/#balls = 1.444444444
Test #11:
score: 0
Accepted
time: 28ms
memory: 3844kb
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 2 14 3 17 4 18 6 15 7 8 9 11 10 13 16 19 7 1 19 2 16 4 15 5 13 6 10 7 11 9 12 -1 10 1 3 2 12 5 4 5 19 6 11 7 17 8 18 9 14 10 15 13 16 11 1 9 3 17 4 19 5 6 5 13 8 14 10 12 15 16 7 15 18 7 18 15 7 1 3 5 9 6 13 8 16 10 14 12 18 17 19 10 3 13 5 3 5 1 2 15 4 6 7 14 8 12 9 16 10 17 11 18 10 1 2 3 19...
result:
ok 9090 cases passed. max #moves/#balls = 1.500000000
Test #12:
score: 0
Accepted
time: 23ms
memory: 3856kb
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 3 6 9 10 15 12 15 11 5 15 8 15 7 8 13 7 13 5 13 2 13 4 5 6 9 7 8 14 7 14 10 1 7 3 14 17 3 17 1 16 14 16 11 12 15 10 1 8 2 14 3 21 4 12 5 11 6 17 7 9 10 18 13 15 16 20 11 1 10 2 9 15 3 12 11 8 12 8 15 13 8 14 8 7 14 5 7 5 13 10 2 19 3 6 4 15 7 10 16 8 5 11 5 16 9 13 12 17 14 18 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: 28ms
memory: 3988kb
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 1 12 2 16 3 20 4 17 5 22 6 10 7 21 8 23 9 18 11 14 13 19 24 25 11 1 15 2 11 9 7 6 16 4 6 4 9 12 13 17 18 10 17 14 10 14 17 9 5 11 10 11 3 10 6 3 6 5 1 6 13 1 12 13 12 6 10 8 13 3 8 1 3 7 5 7 1 12 5 4 12 6 4 14 13 14 6 12 1 10 2 6 3 13 4 20 5 19 7 14 8 22 9 17 11 24 12 21 15 18 16 25 11 2 12 4 5 8...
result:
ok 7692 cases passed. max #moves/#balls = 1.416666667
Test #14:
score: 0
Accepted
time: 24ms
memory: 3932kb
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 6 7 10 9 10 6 12 2 4 3 18 5 7 6 15 8 11 12 13 14 12 19 12 19 14 9 19 21 9 21 19 11 1 14 2 19 3 17 4 12 5 18 6 24 7 9 8 22 10 16 13 23 15 20 12 1 11 2 14 3 17 4 16 10 6 9 7 9 10 8 15 13 20 5 13 19 13 19 5 12 1 27 2 25 3 6 4 20 5 23 7 17 8 14 9 18 10 16 11 19 12 26 21 22 13 1 8 2 9 3 1...
result:
ok 7142 cases passed. max #moves/#balls = 1.384615385
Test #15:
score: 0
Accepted
time: 28ms
memory: 3980kb
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 1 11 2 7 3 17 4 18 9 5 24 21 8 24 10 8 13 10 13 9 12 20 14 22 19 23 13 1 25 2 13 3 4 5 10 6 14 7 18 8 19 9 26 11 15 12 23 16 20 17 22 24 27 12 1 17 3 15 4 21 5 6 8 13 8 11 14 20 19 22 2 19 10 2 7 19 7 10 13 1 3 2 19 4 15 6 21 7 12 8 20 9 10 11 18 14 17 16 25 13 16 23 16 23 13 14 1 27 2 11 3 28 4 ...
result:
ok 6666 cases passed. max #moves/#balls = 1.357142857
Test #16:
score: 0
Accepted
time: 28ms
memory: 3848kb
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 2 3 2 14 4 21 5 6 11 17 10 15 9 10 13 11 13 9 12 11 12 22 8 12 19 8 19 12 13 1 20 17 2 14 17 3 14 24 15 13 24 19 13 19 3 4 8 6 22 10 16 11 12 18 23 12 2 3 8 18 8 5 6 22 7 12 9 14 10 13 15 16 23 24 17 23 19 23 19 17 15 6 17 2 6 16 3 5 16 5 2 10 3 15 5 15 10 11 5 14 6 12 14 12 11 7 12 13 12 13 7 16...
result:
ok 6250 cases passed. max #moves/#balls = 1.400000000
Test #17:
score: 0
Accepted
time: 28ms
memory: 3984kb
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 22 16 22 1 21 16 21 14 2 4 7 5 9 7 18 2 12 18 12 9 23 2 23 19 6 15 8 20 17 13 7 13 2 3 8 4 22 5 10 6 25 23 9 23 17 11 29 12 15 14 19 18 28 21 26 24 27 16 24 20 16 20 24 16 1 11 2 14 24 3 24 15 4 17 6 28 7 25 9 22 10 21 12 23 13 20 16 27 19 26 5 19 18 19 18 5 15 1 13 7 23 8 14 10 19 12 18 15 21 9 ...
result:
ok 5882 cases passed. max #moves/#balls = 1.375000000
Test #18:
score: 0
Accepted
time: 28ms
memory: 3940kb
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 1 15 3 19 4 11 6 33 7 12 8 30 9 18 10 14 13 25 16 22 17 20 21 29 23 31 26 27 28 32 2 28 24 28 24 2 16 1 10 3 19 2 3 2 4 22 3 15 16 8 15 8 22 18 5 18 14 11 23 12 20 9 12 17 9 6 17 6 12 15 6 17 11 6 5 11 16 5 14 16 9 14 20 6 20 9 4 20 13 20 13 4 2 13 18 2 10 18 10 13 18 2 22 3 32 4 24 5 11 6 10 8 1...
result:
ok 5555 cases passed. max #moves/#balls = 1.352941176
Test #19:
score: 0
Accepted
time: 28ms
memory: 3804kb
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 2 5 6 5 19 6 19 2 9 19 10 9 18 10 1 18 11 19 11 1 13 11 16 11 16 13 3 16 14 3 14 16 7 14 12 7 12 14 21 3 20 4 14 5 6 8 25 9 18 10 21 15 16 17 23 11 17 12 11 24 17 26 24 26 12 19 26 22 26 13 22 1 13 1 19 2 1 7 2 7 1 14 6 13 10 12 16 23 11 16 2 11 19 2 7 19 15 16 4 15 20 4 20 7 14 20 17 14 17 20 -1...
result:
ok 5263 cases passed. max #moves/#balls = 1.388888889
Test #20:
score: 0
Accepted
time: 29ms
memory: 3940kb
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 9 3 6 14 10 6 10 9 4 22 13 25 18 24 1 18 12 1 8 12 20 8 11 20 23 11 16 23 15 16 21 13 21 15 17 13 5 18 5 17 18 1 27 2 3 4 13 5 14 7 28 8 31 10 18 11 25 12 16 15 21 19 29 22 20 9 22 17 33 17 9 23 24 26 32 30 34 -1 21 2 9 5 7 11 27 14 19 17 23 18 21 24 25 1 24 15 1 6 18 6 15 8 18 4 24 20 4 20 8 13 ...
result:
ok 5000 cases passed. max #moves/#balls = 1.368421053
Test #21:
score: 0
Accepted
time: 28ms
memory: 3804kb
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 1 18 2 4 3 33 5 30 6 22 7 32 9 19 10 29 11 34 12 35 13 21 14 27 15 28 16 24 17 20 23 26 8 23 25 8 36 25 36 23 22 7 25 9 22 10 11 12 14 26 27 13 26 20 13 18 12 18 20 19 12 24 26 24 19 4 24 15 24 17 15 5 17 5 4 1 5 23 5 2 23 16 2 16 1 21 2 10 4 11 7 13 8 29 9 17 12 16 14 24 18 26 20 22 21 28 23 30 ...
result:
ok 4761 cases passed. max #moves/#balls = 1.300000000
Test #22:
score: 0
Accepted
time: 16ms
memory: 4004kb
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 3 47 17 35 19 23 29 22 29 31 27 62 33 75 36 45 37 41 44 50 40 44 63 40 9 63 26 37 10 26 72 10 72 9 60 37 52 44 52 60 32 52 38 32 15 72 30 15 30 38 20 72 68 30 68 20 79 30 61 52 78 61 78 79 1 78 65 78 16 65 16 1 8 16 69 8 55 68 55 69 67 68 54 67 21 16 21 54 11 21 7 11 6 55 6 7 73 55 74 21 76 74 51...
result:
ok 1000 cases passed. max #moves/#balls = 1.500000000
Test #23:
score: 0
Accepted
time: 16ms
memory: 4128kb
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 2 105 3 75 4 9 5 47 7 37 11 35 12 108 14 30 16 21 17 123 25 90 27 122 32 117 33 115 36 94 40 64 42 52 44 87 45 114 48 92 51 78 54 93 56 112 57 107 59 96 61 98 62 76 73 116 67 73 34 67 34 77 19 73 70 19 63 106 63 70 79 88 82 118 83 119 85 91 95 109 110 113 49 110 102 110 80 102 80 49 55 80 58 55 6...
result:
ok 100 cases passed. max #moves/#balls = 1.169811321
Test #24:
score: 0
Accepted
time: 117ms
memory: 27188kb
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 47930 39403 120612 199994 45526 120612 45526 47930 82791 199994 8600 82791 73469 8600 121113 73469 130069 45526 100144 130069 146839 100144 146839 121113 69274 45526 192298 146839 192298 69274 48529 146839 72878 192298 72878 48529 133198 192298 61006 133198 49920 72878 19140 49920 111450 1914...
result:
ok 1 cases passed. max #moves/#balls = 1.249392470
Test #25:
score: 0
Accepted
time: 122ms
memory: 27060kb
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 87499 466 1886 87499 41252 1886 159869 41252 15716 199939 14654 15716 23686 14654 23686 159869 79718 199939 34240 79718 37452 34240 159098 23686 164285 159098 164285 37452 166588 23686 26215 166588 47492 26215 75168 164285 58350 75168 58350 47492 54982 164285 79811 58350 91593 79811 199135 91...
result:
ok 1 cases passed. max #moves/#balls = 1.248689345
Test #26:
score: 0
Accepted
time: 106ms
memory: 27100kb
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 159225 2791 130502 199158 130502 159225 130400 199158 116378 130400 5219 116378 193254 5219 59594 193254 13400 59594 59402 130502 169530 59402 169530 13400 134704 130502 23501 134704 195483 169530 136282 195483 136282 23501 194296 169530 163027 194296 29741 136282 29741 163027 161399 136282 1...
result:
ok 1 cases passed. max #moves/#balls = 1.249346734
Test #27:
score: 0
Accepted
time: 113ms
memory: 26372kb
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 53513 195490 53513 8 66763 195490 81301 66763 81301 90130 145277 166931 88452 145277 30681 88452 30681 36 187794 38 177176 140533 177176 187794 33449 177176 33449 50 32589 177176 25968 33449 181763 25968 190609 181763 190609 32589 164372 33449 19442 164372 194690 19442 172263 190609 37722 172...
result:
ok 1 cases passed. max #moves/#balls = 1.236284211
Test #28:
score: 0
Accepted
time: 58ms
memory: 17568kb
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 1 19200 127536 17700 127536 3 41165 10 146008 127536 146008 41165 21234 127536 13283 146008 13283 21234 5949 146008 5949 66955 52406 70095 52406 13 14 54179 97745 17288 97745 16 66806 104779 66806 17 82619 20 94208 66806 94208 82619 87896 66806 87896 134836 25 43922 26 145724 51683 28 13132 5...
result:
ok 1 cases passed. max #moves/#balls = 1.110360000
Test #29:
score: 0
Accepted
time: 101ms
memory: 27124kb
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 171410 200000 97712 171410 52612 97712 119503 52612 138016 119503 28740 138016 21514 199999 169576 21514 36185 169576 8836 36185 74434 8836 74434 28740 91173 199999 77064 91173 130769 74434 130769 77064 11747 74434 185560 11747 72711 130769 77786 72711 77786 185560 193153 130769 99645 77786 9...
result:
ok 1 cases passed. max #moves/#balls = 1.250487505