QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#419182 | #2830. Data Structure | jinqihao2023 | AC ✓ | 157ms | 63156kb | C++14 | 3.5kb | 2024-05-23 18:31:33 | 2024-05-23 18:31:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,ax[N],ay[N],d[N],ned[N],l1[N];
int prt[N];
vector<int>bel[N],tr[N];
int gf(int x){if(x==prt[x])return x;return prt[x]=gf(prt[x]);}
void merge(int x,int y){x=gf(x),y=gf(y);if(x!=y)prt[x]=y;}
struct abc{int a,b;};
struct abcd{int to,a;};
vector<abc>op[N],ans;
vector<abcd>son[N],son1[N];
int st[N],top,pos[N],ad[N];
vector<int>all,oth[N];
bool cmp(int a,int b){return ned[a]<ned[b];}
int temp[4];
struct ab
{
int pos,cd,tag;
bool operator < (const ab &a) const
{
if(cd!=a.cd)return cd>a.cd;
return tag>a.tag;
}
};
bool vis[N];
int tot;
void dfs(int x)
{
vis[x]=1,pos[x]=++tot;bool fl=0;
for(auto y:son[x])if(!vis[y.to])dfs(y.to),fl=1;
if(!fl)for(auto y:son1[x])if(!vis[y.to])dfs(y.to);
}
int ct;
void solve()
{
ans.clear(),all.clear();
for(int i=1;i<=n;i++)son[i].clear(),bel[i].clear(),op[i].clear(),prt[i]=i,son1[i].clear();
for(int i=1;i<=n;i++)pos[i]=0,vis[i]=0,ad[i]=0,ax[i]=0,ay[i]=0,d[i]=0,ned[i]=0,oth[i].clear(),tr[i].clear(),pos[i]=0;
for(int i=1;i<=m;i++)l1[i]=0;
for(int i=1;i<=m;i++)
{
int x,y,len;
scanf("%d",&len),l1[i]=len;
if(len==1)
{
scanf("%d",&x);
if(!ax[x])ax[x]=i;else ay[x]=i;
}
else if(len==2)
{
scanf("%d %d",&x,&y);
son[y].push_back((abcd){x,i}),merge(x,y),d[x]++;
son1[x].push_back((abcd){y,i});
ad[x]++,ad[y]++;
if(!ax[x])ax[x]=i;else ay[x]=i;
if(!ax[y])ax[y]=i;else ay[y]=i;
}
}
for(int i=1;i<=n;i++)bel[gf(i)].push_back(i);
st[1]=-3,st[2]=-2,st[3]=-1,top=3;
for(int i=1;i<=n;i++)if(gf(i)==i)
{
priority_queue<ab>q;
tot=0;
int rt=bel[i][0];
for(auto j:bel[i])if(ad[j]==1)rt=j;
dfs(rt);
for(auto j:bel[i])if(d[j]==0)q.push((ab){j,(int)son[j].size(),pos[j]});
if(!q.size())
{
if(bel[i].size()==1)continue;
ned[i]=1;
int len=bel[i].size();
int x=bel[i][0];
op[i].push_back((abc){son1[x][0].a,-1});
int y=son1[x][0].to;
int now=x,lst=son1[x][0].a;
while(son[now][0].to!=x)op[i].push_back((abc){son[now][0].a,lst}),lst=son[now][0].a,now=son[now][0].to;
op[i].push_back((abc){lst,-1});
all.push_back(i),oth[i].push_back(lst);
continue;
}
while(!q.empty())
{
int x=q.top().pos;q.pop();
if(son[x].size()==2)
{
op[i].push_back((abc){ax[x],st[top]});
op[i].push_back((abc){ay[x],st[top]});
top--;
}
else if(son[x].size()==1)
{
int pos=son[x][0].a,pos1;
if(ax[x]!=pos)pos1=ax[x];else pos1=ay[x];
op[i].push_back((abc){pos,pos1});
}
else
{
op[i].push_back((abc){ax[x],ay[x]});
st[++top]=ax[x];
}
for(auto y:son[x])
{
d[y.to]--;
if(!d[y.to])q.push((ab){y.to,(int)son[y.to].size(),pos[y.to]});
}
}
while(top && st[top]>0)oth[i].push_back(st[top]),top--;
ned[i]=-st[top]-1;
all.push_back(i);
st[1]=-3,st[2]=-2,st[3]=-1,top=3;
}
sort(all.begin(),all.end(),cmp);
top=0;
for(int i=1;i<=m;i++)if(!l1[i])st[++top]=i;
for(auto i:all)
{
if(ned[i]>top){printf("-1\n");return ;}
for(int j=1;j<=ned[i];j++)temp[j]=st[top-j+1];
top-=ned[i];
for(auto &j:op[i])
{
if(j.a<0)j.a=temp[-j.a];
if(j.b<0)j.b=temp[-j.b];
}
for(auto j:op[i])ans.push_back(j);
for(auto j:oth[i])st[++top]=j;
}
printf("%d\n",(int)ans.size());
for(auto j:ans)printf("%d %d\n",j.a,j.b);
}
int main()
{
// freopen("cluster.in","r",stdin);
// freopen("cluster.out","w",stdout);
while(~scanf("%d %d",&n,&m))solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 37552kb
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: 4ms
memory: 37348kb
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: 4ms
memory: 38568kb
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 2 3 3 2 4 1 2 1 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: 4ms
memory: 37076kb
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: 3ms
memory: 36972kb
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: 34ms
memory: 37724kb
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: 34ms
memory: 38184kb
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 4 3 1 4 1 3 5 1 8 1 2 8 2 5 7 4 9 1 8 5 1 7 1 3 5 6 7 2 6 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 7 12 2 3 1 11 5 10 6 8 4 9 3 7 6 5 7 3 5 8 5 6 8 6 5 8 1 5 7 5 1 9 4 7 3 4 6 5 9 2 ...
result:
ok 14285 cases passed. max #moves/#balls = 1.500000000
Test #8:
score: 0
Accepted
time: 30ms
memory: 38880kb
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 7 10 5 6 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 5 8 1 7 1 6 4 12 9 11 7 1 6 3 1 10 1 8 10 4 8 7 3 4 7 7 5 12 7 10 8 9 2 11 6 2 3 6 1 4 7 2 10 4 6 5 11 3 4 7 4 7 9 3 5 7 4 1 4 6 2 7 5 9 8 5 10 5 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: 29ms
memory: 38248kb
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 1 9 5 10 8 12 11 8 13 8 4 13 2 11 9 3 1 7 1 5 7 4 3 4 5 8 4 9 4 2 8 2 9 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: 31ms
memory: 38896kb
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 2 1 3 2 3 1 10 3 13 3 10 13 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 6 12 2 7 2 6 4 10 9 17 15 16 5 14 1 13 13 7 4 11 7 11 4 1 11 10 11 1 10 2 1 8 2 8 1 5 8 6 8 9 6 5 9 8 5 ...
result:
ok 10000 cases passed. max #moves/#balls = 1.444444444
Test #11:
score: 0
Accepted
time: 36ms
memory: 36916kb
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 5 4 5 19 6 11 11 4 19 5 6 5 13 10 12 15 16 3 17 1 9 8 14 7 8 18 7 18 8 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: 36ms
memory: 38812kb
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 1 2 14 2 10 14 3 10 16 10 11 16 17 3 1 17 10 6 17 3 21 10 18 7 9 2 14 16 20 5 11 4 12 1 8 13 15 11 2 9 12 11 8 12 15 3 8 15 1 10 13 1 14 1 7 14 5 7 5 13 10 5 11 16 8 5 16 7 10 14 18 3 6 12 17 4 15 2 19 9 13 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: 36ms
memory: 36968kb
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 9 7 6 16 4 6 4 9 12 13 17 18 2 11 14 2 10 14 10 2 9 5 11 10 11 3 10 6 3 5 6 1 5 13 1 12 13 12 5 10 7 13 12 13 4 12 6 4 8 5 14 5 6 14 3 8 1 3 1 7 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 4...
result:
ok 7692 cases passed. max #moves/#balls = 1.416666667
Test #14:
score: 0
Accepted
time: 36ms
memory: 37760kb
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 21 14 9 21 9 14 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 9 7 10 6 9 10 13 20 3 17 4 16 1 11 2 14 5 2 19 2 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: 32ms
memory: 39104kb
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 24 21 8 24 10 8 13 10 9 5 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 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 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: 35ms
memory: 37380kb
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 2 3 2 14 19 2 8 19 8 2 10 15 9 10 12 8 13 8 9 13 12 22 13 6 22 1 20 11 12 4 8 10 16 24 15 13 24 19 13 17 2 14 17 3 14 3 19 18 23 12 10 13 7 12 8 18 5 8 15 16 23 24 6 22 9 14 2 3 17 2 19 2 17 19 15 6 17 7 6 13 6 7 13 2 7 14 7 12 14 11 3 15 3 11 12 10 11 16 11 10 15 5 16 2 5 16 15 19...
result:
ok 6250 cases passed. max #moves/#balls = 1.400000000
Test #17:
score: 0
Accepted
time: 32ms
memory: 37812kb
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 18 8 23 8 19 23 12 18 9 12 21 19 22 19 1 22 14 21 17 12 15 3 8 14 19 4 22 13 7 2 13 23 9 17 23 21 26 6 25 11 29 5 10 24 27 18 28 20 18 16 20 16 18 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 7 ...
result:
ok 5882 cases passed. max #moves/#balls = 1.375000000
Test #18:
score: 0
Accepted
time: 29ms
memory: 38208kb
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 9 14 17 9 6 17 6 14 15 16 8 15 2 6 22 6 2 4 8 22 15 6 17 11 6 20 6 5 11 16 5 14 16 9 14 9 20 10 9 2 10 18 2 18 9 4 18 13 18 4 13 18 25 28 9 21 5 11 13 31 4 24 12 20...
result:
ok 5555 cases passed. max #moves/#balls = 1.352941176
Test #19:
score: 0
Accepted
time: 39ms
memory: 37832kb
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 12 5 7 12 7 5 2 7 6 7 19 6 2 19 9 2 11 2 10 9 18 10 1 18 1 11 3 1 14 3 14 1 13 14 16 14 13 16 21 15 16 9 18 3 20 10 21 5 6 4 14 8 25 17 23 11 17 24 17 12 11 26 24 12 26 19 12 22 12 13 22 1 13 1 19 2 1 7 2 7 1 14 10 12 6 13 16 23 14 16 17 14 17 16 11 17 15 17 2 11 19 2 7 19 4 15 20 4 7 20 -1 16 5 ...
result:
ok 5263 cases passed. max #moves/#balls = 1.388888889
Test #20:
score: 0
Accepted
time: 39ms
memory: 38124kb
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 9 3 6 14 10 6 9 10 18 24 17 18 21 18 1 9 5 9 5 17 12 1 8 12 20 8 11 20 23 11 16 23 15 16 15 21 18 17 33 22 20 9 22 9 17 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 -1 21 24 25 5 7 17 23 14 19 18 21 2 9 11 27 16 11 12 16 12 11 13 12 22 12 13 22 6 13 8 13...
result:
ok 5000 cases passed. max #moves/#balls = 1.368421053
Test #21:
score: 0
Accepted
time: 36ms
memory: 38600kb
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 10 29 12 35 2 4 3 33 7 32 17 20 16 24 11 34 14 27 9 19 13 21 23 26 15 28 6 22 1 18 5 30 8 5 25 8 36 25 36 5 22 12 14 9 22 26 27 7 25 10 11 4 10 15 10 17 15 5 17 4 5 1 4 23 4 2 23 16 2 1 16 18 1 19 1 13 7 24 7 19 24 20 13 18 20 21 12 16 21 28 7 13 14 24 2 10 20 22 9 17 18 26 4 11 8 29 23 30 3 23 1...
result:
ok 4761 cases passed. max #moves/#balls = 1.300000000
Test #22:
score: 0
Accepted
time: 10ms
memory: 38900kb
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 19 23 17 35 3 47 44 50 58 44 77 44 58 77 66 58 46 66 46 58 1 46 65 46 16 65 1 16 57 1 70 57 53 70 53 1 25 53 2 25 2 53 14 2 12 14 71 12 24 71 24 2 34 24 39 34 39 24 42 39 13 42 13 39 6 13 73 13 11 3 74 3 76 74 51 76 48 51 56 48 56 73 7 11 6 7 40 56 52 56 63 40 ...
result:
ok 1000 cases passed. max #moves/#balls = 1.500000000
Test #23:
score: 0
Accepted
time: 18ms
memory: 37804kb
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 17 123 44 87 32 117 3 75 110 113 82 118 61 98 36 94 62 76 7 37 16 21 25 90 95 109 11 35 27 122 42 52 33 115 83 119 4 9 40 64 45 114 48 92 54 93 2 105 79 88 59 96 57 107 85 91 12 108 14 30 5 47 73 116 51 78 56 112 6 56 46 6 46 56 28 46 65 46 28 65 63 106 19 28 67 28 70 19 63 70 34 67 34 77 120 63 ...
result:
ok 100 cases passed. max #moves/#balls = 1.169811321
Test #24:
score: 0
Accepted
time: 150ms
memory: 60956kb
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 72220 199994 127457 199994 71505 72220 29499 71505 65022 127457 1518 65022 160228 1518 43842 160228 4397 29499 144691 29499 43842 144691 177024 43842 197462 43842 4397 177024 179113 197462 75136 4397 165356 4397 174394 165356 174394 179113 107339 75136 145985 107339 7...
result:
ok 1 cases passed. max #moves/#balls = 1.249392470
Test #25:
score: 0
Accepted
time: 157ms
memory: 54536kb
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 78606 55030 188746 78606 51089 145236 197976 51089 175694 197976 40251 199939 183820 199939 124248 183820 2907 124248 76171 2907 116721 76171 92004 116721 92004 188746 100156 40251 38005 92004 113279 92004 100156 113279 88774 100156 190551 100156 38005 190551 56580 88774 175374 56580 158659 1...
result:
ok 1 cases passed. max #moves/#balls = 1.248689345
Test #26:
score: 0
Accepted
time: 147ms
memory: 53728kb
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 89684 177658 177708 198873 2295 177708 190108 2295 28332 199158 49017 199158 28332 89684 151437 49017 145189 28332 155756 28332 145189 151437 29380 145189 196194 145189 169656 29380 129693 169656 192484 129693 155756 192484 124223 196194 118489 124223 5457 155756 90928 155756 5457 118489 1578...
result:
ok 1 cases passed. max #moves/#balls = 1.249346734
Test #27:
score: 0
Accepted
time: 133ms
memory: 53404kb
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 142460 128554 153991 60678 97518 153991 97518 142460 29045 175509 131028 153733 27632 164619 173728 27632 55651 173728 10882 55651 49357 149784 9468 81746 9468 49357 82537 27653 172059 10316 155953 172059 159307 155953 82537 159307 145599 171805 170314 145599 16605 170314 162045 16605 21080 1...
result:
ok 1 cases passed. max #moves/#balls = 1.236284211
Test #28:
score: 0
Accepted
time: 70ms
memory: 46896kb
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 12320 101989 12320 85979 10725 82927 869 124187 91353 119365 82664 126557 50443 82664 147221 115173 39134 147221 39134 87007 36299 149000 96636 103175 50832 96636 113313 64371 32187 113313 73410 142185 55244 86508 80875 81742 101496 1205 27300 101496 103012 6371 85435 103012 11193 81996 13193...
result:
ok 1 cases passed. max #moves/#balls = 1.110360000
Test #29:
score: 0
Accepted
time: 143ms
memory: 63156kb
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 17813 200000 72626 200000 134563 72626 192276 17813 165752 192276 5262 199999 30899 199999 5262 165752 37687 30899 43247 5262 181997 5262 37687 181997 24936 37687 190474 37687 130329 24936 130371 130329 43247 130371 24554 43247 140583 43247 142584 24554 142584 190474 121932 142584 151951 1425...
result:
ok 1 cases passed. max #moves/#balls = 1.250487505