QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#385581 | #2830. Data Structure | ucup-team1209 | AC ✓ | 292ms | 36624kb | C++14 | 3.4kb | 2024-04-10 21:25:18 | 2024-04-10 21:25:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
#ifdef zqj
freopen("a.in","r",stdin);
#endif
}
typedef long long ll;
#define sz 202020
int n,m;
vector<int>st[sz];
vector<int>pos[sz];
set<int>num[3];
vector<pii>ans;
void output() {
cout<<ans.size()<<'\n';
for (auto [x,y]:ans) cout<<x<<' '<<y<<'\n';
}
void mov(int f,int t) {
assert(f!=t);
assert(st[f].size());
assert(st[t].size()==0u||(st[t].size()==1u&&st[t][0]==st[f].back()));
for (auto p:{f,t}) num[st[p].size()].erase(p);
ans.push_back({f,t});
int x=st[f].back();
st[t].push_back(x),st[f].pop_back();
rep(i,0,1) if (pos[x][i]==f) {pos[x][i]=t; break;}
num[st[f].size()].insert(f);
if (st[t].size()!=1u) num[st[t].size()].insert(t);
}
int ok(int x){return pos[x][0]==pos[x][1];}
void check(int x) {
assert(!ok(x));
int p0=pos[x][0],p1=pos[x][1];
if (st[p1].size()==1u) swap(p0,p1);
if (st[p0].size()==1u) {
if (st[p1].size()==1u||st[p1][1]==x) {
mov(p1,p0);
if (st[p1].size()) check(st[p1][0]);
return;
}
if (num[0].size()) {
int pp=*(num[0].begin()),t=p1;
while (233) {
int y=st[t][1];
t^=pos[y][0]^pos[y][1];
if (st[t].size()==1u) return check(st[t][0]);
if (st[t][1]==y) {
int yy=st[t][0];
mov(t,pp);
check(y);
check(yy);
return;
}
}
}
}
}
void work() {
#define NO return cout<<"-1\n",void()
rep(i,1,m) st[i].clear();
rep(i,1,n) pos[i].clear();
rep(i,0,2) num[i].clear();
ans.clear();
rep(i,1,m) {
int k,x; cin>>k;
rep(_,1,k) cin>>x,st[i].push_back(x),pos[x].push_back(i);
if (k!=2||(k==2&&st[i][0]!=st[i][1])) num[k].insert(i);
}
if (n==m) {
if (num[2].size()) NO;
output();
return;
}
rep(i,1,n) if (!ok(i)) check(i);
if (num[1].size()||num[2].size()) {
if (!num[0].size()) NO;
while (num[1].size()) {
int p=*(num[1].begin());
check(st[p][0]);
}
assert(num[0].size());
rep(i,1,n) if (!ok(i)&&st[pos[i][0]][1]==i&&st[pos[i][1]][1]==i) {
int pp=*(num[0].begin()),p0=pos[i][0],p1=pos[i][1];
mov(p0,pp),mov(p1,pp);
check(st[p0].back());
if (st[p1].size()&&!ok(st[p1][0])) check(st[p1].back());
if (!num[0].size()) {
assert(m==n+1);
NO;
}
}
rep(i,1,n) if (!ok(i)) {
int pp=*(num[0].begin()),p0=pos[i][0],p1=pos[i][1];
if (st[p0][1]!=i) swap(p0,p1);
mov(p0,pp);
check(st[p0].back());
assert(num[0].size());
}
rep(i,1,n) assert(ok(i));
}
output();
}
int main() {
file();
ios::sync_with_stdio(false),cin.tie(0);
while (cin>>n>>m) work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 13164kb
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: 3ms
memory: 13196kb
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: 13204kb
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 1 4 1 2 4 -1 3 2 3 1 2 1 3 3 1 3 2 1 3 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: 2ms
memory: 13152kb
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: 4ms
memory: 13212kb
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: 32ms
memory: 13100kb
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: 38ms
memory: 13148kb
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 10 8 3 10 4 7 1 6 2 9 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 6 7 2 6 3 5 5 2 7 5 2 3 5 4 1 3 4 5 6 3 2 6 7 1 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 7 2 1 2 1 9 4 7 3 4 5 1 8 1 5 8 6 5 9 2 ...
result:
ok 14285 cases passed. max #moves/#balls = 1.500000000
Test #8:
score: 0
Accepted
time: 39ms
memory: 13144kb
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 5 6 1 11 7 10 5 7 4 9 2 3 8 12 7 8 13 3 15 9 14 1 4 6 12 2 5 7 11 -1 7 7 10 1 5 3 1 3 11 4 8 6 9 2 12 7 10 13 3 14 1 7 1 6 5 8 4 12 9 11 7 1 6 3 1 10 1 7 3 8 10 4 8 4 7 7 5 12 7 10 8 9 2 11 6 2 3 6 1 4 7 2 10 5 11 7 1 3 1 3 5 7 9 4 6 7 4 1 4 6 2 7 5 9 8 2 10 2 8 10 7 4 5 3 8 14 1...
result:
ok 12500 cases passed. max #moves/#balls = 1.428571429
Test #9:
score: 0
Accepted
time: 37ms
memory: 13092kb
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 12 9 2 12 4 10 7 13 1 11 5 1 6 1 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 13 3 11 3 2 11 4 13 1 9 5 10 8 12 9 8 1 9 1 2 8 2 9 3 2 7 2 4 3 5 7 4 5 7 2 6 1 2 8 2 10 1 4 10 5 8 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: 40ms
memory: 13168kb
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 4 11 1 4 6 8 5 12 10 1 13 1 10 13 3 5 2 3 2 5 11 11 12 1 5 4 1 9 1 8 7 2 7 3 2 6 3 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 1 9 1 5 9 2 5 9 3 11 2 7 6 12 2 6 4 10 9 17 15 16 5 14 1 13 13 1 3 10 3 1 10 5 1 6 1 9 6 5 9 11 4 7 11 7 4 8 5 2 8 2 5 8 5 12 1...
result:
ok 10000 cases passed. max #moves/#balls = 1.444444444
Test #11:
score: 0
Accepted
time: 38ms
memory: 13156kb
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 5 4 5 19 1 3 2 12 9 14 8 18 10 15 6 11 11 4 19 5 6 5 13 10 12 15 16 3 17 1 9 8 14 18 1 7 18 7 1 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 3 13 5 3 1 5 2 15 11 18 10 8 12 10 13...
result:
ok 9090 cases passed. max #moves/#balls = 1.500000000
Test #12:
score: 0
Accepted
time: 39ms
memory: 13156kb
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 3 8 3 7 8 13 7 5 13 13 12 15 7 8 3 7 16 7 11 16 17 3 14 11 1 11 1 17 10 14 6 9 4 5 2 13 10 6 17 3 21 10 18 7 9 2 14 16 20 5 11 4 12 1 8 13 15 11 2 9 15 3 12 11 8 12 8 15 1 10 13 1 14 1 7 14 5 7 5 13 10 16 8 7 10 5 11 5 16 14 18 3 6 12 17 4 15 2 19 9 13 11 7 10 7 12 1 7 4 7 3...
result:
ok 8333 cases passed. max #moves/#balls = 1.363636364
Test #13:
score: 0
Accepted
time: 44ms
memory: 13224kb
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 6 16 4 6 9 7 4 9 12 13 17 18 2 11 10 1 14 10 1 14 9 5 7 10 7 3 10 6 3 5 6 13 5 12 13 1 12 1 5 10 8 5 14 5 3 8 1 3 12 13 7 13 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 8 2 1...
result:
ok 7692 cases passed. max #moves/#balls = 1.416666667
Test #14:
score: 0
Accepted
time: 41ms
memory: 13216kb
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 8 10 8 6 7 6 10 12 6 15 3 18 8 11 12 13 2 4 5 7 14 2 19 2 14 19 9 3 21 9 3 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 10 6 9 7 9 10 13 20 3 17 4 16 1 11 2 14 5 1 19 1 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 5 ...
result:
ok 7142 cases passed. max #moves/#balls = 1.384615385
Test #15:
score: 0
Accepted
time: 45ms
memory: 13228kb
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 9 5 24 21 8 24 10 8 13 10 9 13 19 23 4 18 12 20 2 7 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 8 13 8 11 3 15 5 6 4 21 14 20 1 17 2 1 7 1 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 1 23 1 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: 45ms
memory: 13156kb
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 13 1 12 1 12 22 10 15 9 10 9 13 4 21 11 17 2 3 2 14 5 6 8 2 19 8 2 19 13 6 22 1 20 11 12 17 2 14 17 3 14 24 15 13 24 19 13 3 19 4 8 10 16 18 23 12 10 13 7 12 8 18 5 8 15 16 23 24 6 22 9 14 2 3 17 1 19 1 17 19 15 6 17 2 3 14 3 10 6 16 6 5 16 2 5 11 2 15 2 10 15 12 14 11 12 7 10 13 10 7 13 16 15 19...
result:
ok 6250 cases passed. max #moves/#balls = 1.400000000
Test #17:
score: 0
Accepted
time: 43ms
memory: 13216kb
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 3 21 3 14 21 1 22 6 15 18 1 23 1 19 23 12 18 7 5 9 7 9 12 2 4 8 20 17 12 15 3 8 14 19 13 7 2 13 4 22 23 9 17 23 21 26 6 25 11 29 5 10 24 27 18 28 16 1 20 16 1 20 16 13 20 7 25 16 27 6 28 19 26 12 23 9 22 2 14 24 3 15 24 10 21 4 17 1 11 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: 47ms
memory: 13160kb
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 1 24 1 2 24 16 3 19 12 20 11 23 1 10 18 5 14 18 15 16 8 15 2 1 22 1 8 22 2 4 17 2 6 17 9 6 9 2 15 6 17 11 6 20 6 5 11 16 5 14 16 9 14 9 20 4 7 13 7 4 13 2 4 18 2 10 18 4 10 18 30 1 7 1 7 27 26 30 25 28 9 21 5 11 ...
result:
ok 5555 cases passed. max #moves/#balls = 1.352941176
Test #19:
score: 0
Accepted
time: 47ms
memory: 13100kb
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 2 19 9 2 11 2 10 9 18 10 1 18 1 11 13 1 16 1 13 16 14 13 3 14 3 13 7 3 12 7 3 12 21 15 16 9 18 3 20 10 21 5 6 4 14 8 25 17 23 11 3 24 3 12 11 26 24 12 26 19 4 22 4 13 22 1 13 1 19 7 1 2 7 2 1 14 10 12 6 13 16 23 11 6 15 6 2 11 19 2 7 19 4 15 20 4 7 20 17 7 14 17 14 7 -1 16 5 16 2 5 1...
result:
ok 5263 cases passed. max #moves/#balls = 1.388888889
Test #20:
score: 0
Accepted
time: 47ms
memory: 13224kb
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 6 14 10 6 9 3 9 10 18 24 1 2 5 2 12 1 8 12 20 8 11 20 23 11 16 23 15 16 17 4 21 4 15 21 5 17 18 22 20 9 22 26 32 15 21 17 33 9 17 5 14 4 13 7 28 30 34 10 18 1 27 11 25 12 16 19 29 2 3 23 24 8 31 -1 21 24 25 5 7 17 23 14 19 18 21 2 9 11 27 1 2 4 2 15 1 8 3 6 3 6 15 20 4 8 20 13 5 22 5 1...
result:
ok 5000 cases passed. max #moves/#balls = 1.368421053
Test #21:
score: 0
Accepted
time: 44ms
memory: 13172kb
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 25 1 36 25 8 36 8 1 22 12 14 9 22 26 27 7 25 10 11 13 3 24 3 20 13 19 6 18 6 18 20 19 24 4 7 15 7 17 15 5 17 4 5 1 4 23 4 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 3 2 19 2...
result:
ok 4761 cases passed. max #moves/#balls = 1.300000000
Test #22:
score: 0
Accepted
time: 24ms
memory: 13172kb
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 29 22 29 31 37 41 33 75 27 62 17 35 3 47 44 50 19 23 40 3 52 3 63 40 9 63 60 17 26 17 10 26 72 10 9 72 52 60 32 9 61 9 38 32 20 19 15 19 30 15 30 38 79 27 68 27 20 68 78 61 78 79 1 20 65 20 16 65 1 16 8 1 21 1 69 8 67 29 55 29 55 69 54 67 21 54 11 21 74 21 7 11 73 30 6 30 6 7 76 74 51 76 48...
result:
ok 1000 cases passed. max #moves/#balls = 1.500000000
Test #23:
score: 0
Accepted
time: 34ms
memory: 13404kb
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 19 2 67 2 34 67 34 77 70 19 63 106 63 70 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 49 3 102 3 80 102 49 80 55 4 60 4 58 55 58 ...
result:
ok 100 cases passed. max #moves/#balls = 1.169811321
Test #24:
score: 0
Accepted
time: 260ms
memory: 36624kb
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 33532 199993 149868 199993 55718 149868 55718 174021 40140 55718 154492 55718 98071 154492 33532 98071 3409 40140 127577 3409 183763 33532 146781 33532 127577 146781 177569 183763 39870 177569 128051 39870 40416 128051 47653 40416 24457 47653 139428 24457 94458 139428 3940 127577 78541 127577...
result:
ok 1 cases passed. max #moves/#balls = 1.249392470
Test #25:
score: 0
Accepted
time: 273ms
memory: 36576kb
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 61879 106581 58652 199938 173762 199938 61879 173762 10636 58652 101776 61879 53630 61879 160710 53630 38522 160710 10636 38522 183655 10636 154767 10636 42645 154767 36502 42645 36502 101776 139484 183655 148363 36502 17420 36502 98577 17420 145079 98577 139484 145079 65955 148...
result:
ok 1 cases passed. max #moves/#balls = 1.248689345
Test #26:
score: 0
Accepted
time: 282ms
memory: 36500kb
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 83406 199157 84174 199157 26569 84174 26569 188145 51106 83406 52620 26569 39533 26569 39533 51106 146489 39533 5736 39533 105904 5736 87709 105904 52620 87709 154600 146489 101799 154600 140533 101799 170499 140533 61933 52620 37206 52620 37206 170499 175514 37206 147032 37206 116054 147032 ...
result:
ok 1 cases passed. max #moves/#balls = 1.249346734
Test #27:
score: 0
Accepted
time: 292ms
memory: 36032kb
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 171028 51311 63100 852 126434 852 126434 171028 148807 1964 166960 1964 63100 166960 100765 2210 1365 2210 1365 148807 87660 1365 94533 1365 30322 94533 30322 100765 148727 2559 86374 2559 152516 86374 87660 152516 65549 148727 57090 3305 149132 3305 65549 149132 68780 57090 78644 3407 128694...
result:
ok 1 cases passed. max #moves/#balls = 1.236284211
Test #28:
score: 0
Accepted
time: 157ms
memory: 28060kb
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 111937 43798 56855 111937 27095 32591 27095 103272 131140 4 150754 4 78320 150754 92422 131480 92422 131140 23954 65389 18074 5 145511 5 23954 145511 118111 18074 118111 139104 56699 110128 145196 56699 46437 145196 75012 132794 7207 75012 25486 7207 68460 11 50840 11 19502 50840 109500 19502...
result:
ok 1 cases passed. max #moves/#balls = 1.110360000
Test #29:
score: 0
Accepted
time: 249ms
memory: 36596kb
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 199999 181365 199999 97712 171410 52612 97712 119503 52612 138016 119503 28740 138016 91173 200000 21514 200000 169576 21514 36185 169576 8836 36185 74434 8836 28740 74434 77064 91173 11747 28740 130769 28740 77064 130769 185560 11747 193153 77064 72711 77064 77786 72711 77786 185560 1...
result:
ok 1 cases passed. max #moves/#balls = 1.250487505