QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#562632 | #9295. Treeshop | zjy0001 | WA | 7ms | 117068kb | C++17 | 10.5kb | 2024-09-13 19:36:42 | 2024-09-13 19:36:43 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
const int N=2e5+5,INF=1e9;
struct Tree{
int n,tim,D,cnt;
vector<int>G[N];
int sz[N],son[N],d[N],f[N],top[N],dL[N],dR[N],bl[N],rk[N];
int dp[N],dq[N],fdp[3][N],fdq[3][N],gdp[3][N],gdq[3][N],sbl[N];
inline void init(int _n){
n=_n;
}
inline void add(int u,int v){
G[u].emplace_back(v);
G[v].emplace_back(u);
}
inline void dfs1(int u,int fa){
sz[u]=1,son[u]=0,f[u]=fa,d[u]=fa?d[fa]+1:0;
for(auto v:G[u])if(v!=fa)dfs1(v,u),sz[u]+=sz[v],sz[son[u]]<sz[v]?son[u]=v:0;
}
inline void dfs2(int u,int fa,int tp){
top[u]=tp,rk[dL[u]=++tim]=u;
if(son[u])dfs2(son[u],u,tp);
for(auto v:G[u])if(v!=fa&&v!=son[u])dfs2(v,u,v);
dR[u]=tim;
}
inline int LCA(int x,int y){
for(;top[x]!=top[y];dL[top[x]]>dL[top[y]]?x=f[top[x]]:y=f[top[y]]);
return dL[x]<dL[y]?x:y;
}
inline int dist(int x,int y){
return d[x]+d[y]-d[LCA(x,y)]*2;
}
struct{
int a[N],dq[N],df[N];
int ST[20][N];
pair<int,int>dp[N][3],tmp[6];
int n,*sz,*d,*top,*dL,*dR,*rk,*f;
vector<int>*G;
inline int LCA(int x,int y){
for(;top[x]!=top[y];dL[top[x]]>dL[top[y]]?x=f[top[x]]:y=f[top[y]]);
return dL[x]<dL[y]?x:y;
}
inline int dist(int x,int y){
return d[x]+d[y]-d[LCA(x,y)]*2;
}
inline void Dp1(int u,int fa){
df[u]=-INF,dq[u]=-INF;
dp[u][0]=dp[u][1]=dp[u][2]=make_pair(-INF,0);
if(a[u])dp[u][0]=make_pair(0,u);
for(auto v:G[u])if(v!=fa){
Dp1(v,u);
if(dp[v][0].first+1>dp[u][0].first)
dp[u][2]=dp[u][1],dp[u][1]=dp[u][0],dp[u][0]=make_pair(dp[v][0].first+1,v);
else if(dp[v][0].first+1>dp[u][1].first)
dp[u][2]=dp[u][1],dp[u][1]=make_pair(dp[v][0].first+1,v);
else dp[u][2]=max(dp[u][2],make_pair(dp[v][0].first+1,v));
}
}
inline void Dp2(int u,int fa){
for(auto v:G[u])if(v!=fa)
if(dp[u][0]==make_pair(dp[v][0].first+1,v))df[v]=dp[u][1].first;
else df[v]=dp[u][0].first;
int mx=dp[u][0].first,se=dp[u][1].first;
if(a[u])dq[u]=max(dq[u],0);
if(mx<dq[u])se=mx,mx=dq[u];
else se=max(se,dq[u]);
for(auto v:G[u])if(v!=fa){
if(mx==dp[v][0].first+1)dq[v]=se+1;
else dq[v]=mx+1;
Dp2(v,u);
}
}
inline void init(){
Dp1(1,0),Dp2(1,0);
for(int i=1;i<=n;++i)ST[0][dL[i]]=df[i];
for(int j=0,jj=1;jj<=n;++j,jj*=2)
for(int i=n-jj*2+1;i>=1;--i)
ST[j+1][i]=max(ST[j][i],ST[j][i+jj]);
}
inline int qry(int l,int r){
if(l>r)return -INF;
const int t=__lg(r-l+1);
return max(ST[t][l],ST[t][r-(1<<t)+1]);
}
inline int solve(int u,int v){
if(u==v)return max(dp[u][0].first,dq[u])*2;
int bas=dist(u,v);
if(dL[u]>dL[v])swap(u,v);
if(dL[u]<=dL[v]&&dL[v]<=dR[u]){
int ans=max(0,dp[v][0].first);
for(;d[top[v]]>=d[u]+1;v=f[top[v]])ans=max(ans,qry(dL[top[v]],dL[v]));
if(d[u]+1<=d[v])ans=max(ans,qry(dL[top[v]]+d[u]-d[top[v]]+1,dL[v]));
ans=max(ans,dq[u]);
return ans*2+bas;
}
int ans=max(dp[u][0].first,dp[v][0].first),p=LCA(u,v);
for(;d[top[u]]>=d[p]+2;u=f[top[u]])ans=max(ans,qry(dL[top[u]],dL[u]));
if(d[p]+2<=d[u])ans=max(ans,qry(dL[top[u]]+d[p]-d[top[u]]+2,dL[u]));
for(;d[top[v]]>=d[p]+2;v=f[top[v]])ans=max(ans,qry(dL[top[v]],dL[v]));
if(d[p]+2<=d[v])ans=max(ans,qry(dL[top[v]]+d[p]-d[top[v]]+2,dL[v]));
if(d[top[u]]>d[p]+1)u=f[top[u]];else u=rk[dL[top[u]]+d[p]-d[top[u]]+1];
if(d[top[v]]>d[p]+1)v=f[top[v]];else v=rk[dL[top[v]]+d[p]-d[top[v]]+1];
if(dp[p][0].second!=u&&dp[p][0].second!=v)ans=max(ans,dp[p][0].first);
else if(dp[p][1].second!=u&&dp[p][1].second!=v)ans=max(ans,dp[p][1].first);
else ans=max(ans,dp[p][2].first);
ans=max(ans,dq[p]);
return ans*2+bas;
}
}T,H;
inline void dfs(int u,int fa,int k){
sbl[u]=k;
if(G[u].size()==1)bl[u]=k;
for(auto v:G[u])if(v!=fa)dfs(v,u,k);
}
inline void Dp1(int u,int fa){
if(bl[u])dp[u]=u;
for(auto v:G[u])if(v!=fa){
Dp1(v,u);
if(dp[v]){
if(!dp[u]||dist(dp[u],u)<dist(dp[v],u))dq[u]=dp[u],dp[u]=dp[v];
else if(!dq[u]||dist(dq[u],u)<dist(dp[v],u))dq[u]=dp[v];
}
}
}
inline void Dp2(int u,int fa){
for(auto v:G[u])if(v!=fa){
if(dp[u]){
if(!dp[v]||dist(dp[v],v)<dist(dp[u],v))dq[v]=dp[v],dp[v]=dp[u];
else if(dp[u]!=dp[v]&&(!dq[v]||dist(dq[v],v)<dist(dp[u],v)))dq[v]=dp[u];
}
if(dq[u]){
if(!dp[v]||dist(dp[v],v)<dist(dq[u],v))dq[v]=dp[v],dp[v]=dq[u];
else if(dq[u]!=dp[v]&&(!dq[v]||dist(dq[v],v)<dist(dq[u],v)))dq[v]=dq[u];
}
Dp2(v,u);
}
}
inline void Dp3(int u,int fa,int k){
gdp[k][u]=(bl[u]==3-k?u:0);
for(auto v:G[u])if(v!=fa){
Dp3(v,u,k);
if(gdp[k][v]){
if(!gdp[k][u]||dist(gdp[k][u],u)<dist(gdp[k][v],u))gdq[k][u]=gdp[k][u],gdp[k][u]=gdp[k][v];
else if(!gdq[k][u]||dist(gdq[k][u],u)<dist(gdp[k][v],u))gdq[k][u]=gdp[k][v];
}
}
}
inline void Dp4(int u,int fa,int k){
for(auto v:G[u])if(v!=fa){
if(gdp[k][u]){
if(!gdp[k][v]||dist(gdp[k][v],v)<dist(gdp[k][u],v))gdq[k][v]=gdp[k][v],gdp[k][v]=gdp[k][u];
else if(gdp[k][u]!=gdp[k][v]&&(!gdq[k][v]||dist(gdq[k][v],v)<dist(gdp[k][u],v)))gdq[k][v]=gdp[k][u];
}
if(gdq[k][u]){
if(!gdp[k][v]||dist(gdp[k][v],v)<dist(gdq[k][u],v))gdq[k][v]=gdp[k][v],gdp[k][v]=gdq[k][u];
else if(gdq[k][u]!=gdp[k][v]&&(!gdq[k][v]||dist(gdq[k][v],v)<dist(gdq[k][u],v)))gdq[k][v]=gdq[k][u];
}
Dp4(v,u,k);
}
}
inline void Dp5(int u,int fa,int k){
fdp[k][u]=u;
for(auto v:G[u])if(v!=fa){
Dp5(v,u,k);
if(fdp[k][v]){
if(!fdp[k][u]||dist(fdp[k][u],u)+gdp[k][fdp[k][u]]<dist(fdp[k][v],u)+gdp[k][fdp[k][v]])fdq[k][u]=fdp[k][u],fdp[k][u]=fdp[k][v];
else if(!fdq[k][u]||dist(fdq[k][u],u)+gdp[k][fdq[k][u]]<dist(fdp[k][v],u)+gdp[k][fdp[k][v]])fdq[k][u]=fdp[k][v];
}
}
}
inline void Dp6(int u,int fa,int k){
for(auto v:G[u])if(v!=fa){
if(fdp[k][u]){
if(!fdp[k][v]||dist(fdp[k][v],v)+gdp[k][fdp[k][v]]<dist(fdp[k][u],v)+gdp[k][fdp[k][u]])fdq[k][v]=fdp[k][v],fdp[k][v]=fdp[k][u];
else if(fdp[k][u]!=fdp[k][v]&&(!fdq[k][v]||dist(fdq[k][v],v)+gdp[k][fdq[k][v]]<dist(fdp[k][u],v)+gdp[k][fdp[k][u]]))fdq[k][v]=fdp[k][u];
}
if(fdq[k][u]){
if(!fdp[k][v]||dist(fdp[k][v],v)+gdp[k][fdp[k][v]]<dist(fdq[k][u],v)+gdp[k][fdq[k][u]])fdq[k][v]=fdp[k][v],fdp[k][v]=fdq[k][u];
else if(fdq[k][u]!=fdp[k][v]&&(!fdq[k][v]||dist(fdq[k][v],v)+gdp[k][fdq[k][v]]<dist(fdq[k][u],v)+gdp[k][fdq[k][u]]))fdq[k][v]=fdq[k][u];
}
Dp6(v,u,k);
}
}
inline void build(){
dfs1(1,0),dfs2(1,0,1);
int rtx=1,rty=1,rt=0;
for(int i=1;i<=n;++i)if(d[i]>d[rtx])rtx=i;
for(int i=1;i<=n;++i)if(dist(rtx,i)>dist(rtx,rty))rty=i;
if(d[rtx]>d[rty])swap(rtx,rty);
D=dist(rtx,rty),rt=rty;
for(int i=0;i<D/2;++i)rt=f[rt];
if(D&1)dfs(rt,f[rt],++cnt),dfs(f[rt],rt,++cnt);
else for(auto v:G[rt])dfs(v,rt,++cnt);
Dp1(1,0),Dp2(1,0);
for(int i=1;i<=n;++i)dp[i]=dist(dp[i],i);
if(cnt==2){
Dp3(1,0,1),Dp4(1,0,1),Dp3(1,0,2),Dp4(1,0,2);
for(int j=1;j<3;++j)for(int i=1;i<=n;++i)gdp[j][i]=dist(gdp[j][i],i);
Dp5(1,0,1),Dp6(1,0,1),Dp5(1,0,2),Dp6(1,0,2);
for(int j=1;j<3;++j)for(int i=1;i<=n;++i)fdp[j][i]=gdp[j][fdp[j][i]]+dist(fdp[j][i],i);
}
for(int i=1;i<=n;++i)H.a[i]=1,T.a[i]=bl[i];
H.d=d,H.dL=dL,H.dR=dR,H.G=G,H.n=n,H.rk=rk,H.sz=sz,H.top=top,H.f=f;
T.d=d,T.dL=dL,T.dR=dR,T.G=G,T.n=n,T.rk=rk,T.sz=sz,T.top=top,T.f=f;
H.init(),T.init();
}
inline int solve(int u,int v,int L){
if(H.solve(u,v)>=L)return 2;
int sa=0,sb=T.solve(u,v);
if(!sbl[u]||!sbl[v]||sbl[u]!=sbl[v]||cnt>2)sa=D+dp[u]+dp[v];
else sa=max(dp[u]+fdp[sbl[v]][v],dp[v]+fdp[sbl[u]][u]);
return min(max(0,(L-sa+D+D-1)/(D+D)*2)+3,max(0,(L-sb+D+D-1)/(D+D)*2)+2);
}
}T1,T2;
int n,m,q;
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>m>>q;
T1.init(n);
for(int i=1;i<n;++i){
int u,v;cin>>u>>v;
T1.add(u,v);
}
T2.init(m);
for(int i=1;i<m;++i){
int u,v;cin>>u>>v;
T2.add(u,v);
}
if(min(n,m)<2){
for(int i=1;i<=q;++i){
int u,x,v,y;cin>>u>>x>>v>>y;
if(u==v&&x==y)cout<<"0\n";
else cout<<"-1\n";
}
return 0;
}
T1.build();
T2.build();
for(int i=1;i<=q;++i){
int u,x,v,y;cin>>u>>x>>v>>y;
int duv=T1.dist(u,v),dxy=T2.dist(x,y);
if(duv==dxy)cout<<min(duv,1)<<'\n';
else if(duv%2!=dxy%2)cout<<"-1\n";
else if(duv<dxy)cout<<T1.solve(u,v,dxy)<<'\n';
else cout<<T2.solve(x,y,duv)<<'\n';
}
return 0;
}
/*
21 56 1
1 2
1 3
2 18
18 4
2 5
3 19
19 6
3 20
20 7
4 8
6 9
6 10
7 11
8 12
9 13
10 14
11 15
12 16
14 17
3 21
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
6 1 6 51
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 85940kb
input:
4 5 7 1 2 2 3 2 4 1 2 2 3 3 4 4 5 1 1 2 5 1 5 4 1 1 5 4 2 2 5 2 3 2 1 2 5 3 2 3 2 4 4 1 2
output:
-1 2 -1 2 3 0 1
result:
ok 7 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 40820kb
input:
1 3 4 1 2 2 3 1 1 1 1 1 2 1 2 1 2 1 3 1 1 1 3
output:
0 0 -1 -1
result:
ok 4 number(s): "0 0 -1 -1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 96092kb
input:
6 2 18 1 2 2 3 3 4 4 5 5 6 1 2 1 1 1 2 1 1 2 2 1 1 3 2 1 1 4 2 1 1 5 2 1 1 6 2 1 1 1 1 1 1 2 1 1 1 3 1 1 1 4 1 1 1 5 1 1 1 6 1 1 2 1 2 1 2 2 2 1 2 3 2 1 2 4 2 1 2 5 2 1 2 6 2
output:
-1 1 -1 3 -1 5 0 -1 2 -1 4 -1 0 -1 2 -1 4 -1
result:
ok 18 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 100280kb
input:
21 65 8 1 2 1 3 2 18 18 4 2 5 3 19 19 6 3 20 20 7 4 8 6 9 6 10 7 11 8 12 9 13 10 14 11 15 12 16 14 17 3 21 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 ...
output:
6 6 5 5 6 6 5 5
result:
ok 8 numbers
Test #5:
score: 0
Accepted
time: 3ms
memory: 94012kb
input:
10 15 10 9 10 9 3 8 3 4 8 1 4 1 6 4 5 7 5 1 2 8 9 9 10 10 2 15 2 5 15 5 1 1 3 3 13 4 13 11 4 1 6 6 14 7 6 12 7 8 12 2 7 6 14 1 11 1 6 7 5 5 2 5 11 3 13 8 10 5 6 7 6 7 11 10 11 8 1 6 6 10 11 2 13 6 10 7 12
output:
2 -1 -1 -1 -1 -1 2 2 2 -1
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 40880kb
input:
1 15 10 14 2 14 15 13 15 5 13 8 5 8 4 4 7 9 7 11 9 11 3 4 6 10 13 10 1 12 8 1 6 1 7 1 6 1 12 1 2 1 12 1 3 1 8 1 8 1 10 1 12 1 2 1 4 1 5 1 12 1 10 1 3 1 3 1 12 1 9
output:
-1 -1 -1 -1 -1 -1 -1 -1 0 -1
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 3ms
memory: 40752kb
input:
1 1 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 40756kb
input:
25 1 10 12 3 3 25 4 25 8 4 8 9 9 18 18 6 24 6 24 1 11 1 2 9 6 5 15 5 15 7 25 21 16 21 14 1 23 2 23 19 19 10 22 8 13 22 20 13 17 8 1 1 21 1 3 1 2 1 18 1 13 1 7 1 3 1 20 1 11 1 7 1 13 1 18 1 5 1 16 1 1 1 2 1 22 1 24 1 16 1
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
ok 10 numbers
Test #9:
score: 0
Accepted
time: 4ms
memory: 92016kb
input:
14 15 30 3 5 8 5 7 8 7 4 4 13 13 11 11 14 14 10 12 4 12 1 2 13 6 2 9 6 3 12 7 3 7 11 11 10 9 10 9 6 3 5 14 9 2 3 7 1 10 4 4 15 13 10 1 8 14 2 12 6 2 14 1 8 8 4 14 11 3 14 5 3 7 10 6 11 11 9 6 10 13 4 6 5 12 3 14 3 5 6 12 11 2 4 6 8 11 12 6 4 2 13 8 11 2 4 2 12 12 6 8 15 3 11 5 12 9 3 2 14 2 11 1 8 8...
output:
2 2 -1 2 -1 2 -1 2 -1 2 2 2 -1 -1 2 -1 -1 -1 2 -1 2 -1 -1 -1 2 -1 -1 2 -1 -1
result:
ok 30 numbers
Test #10:
score: 0
Accepted
time: 0ms
memory: 96044kb
input:
14 15 30 14 1 7 1 7 2 6 2 8 6 8 13 10 13 2 3 5 3 8 4 3 12 11 7 1 9 7 15 7 1 4 1 3 4 3 13 2 13 2 14 8 4 6 8 12 6 3 9 5 9 4 11 11 10 13 8 2 2 1 15 6 7 10 9 9 1 12 6 13 15 6 13 3 12 8 3 2 9 11 2 14 5 8 7 8 5 2 1 6 1 9 12 7 5 3 13 3 12 11 4 7 4 11 8 10 1 11 1 6 2 9 8 2 12 4 9 5 7 9 12 7 6 14 2 2 2 6 3 6...
output:
-1 2 2 1 -1 -1 -1 -1 -1 2 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 2 1 2 -1 -1 1 -1 -1 2 2
result:
ok 30 numbers
Test #11:
score: 0
Accepted
time: 3ms
memory: 87920kb
input:
20 15 30 16 19 19 14 3 14 1 3 20 1 17 20 1 18 9 3 9 10 15 10 9 7 12 14 5 12 11 20 4 7 2 3 13 3 19 6 8 1 4 15 15 6 12 6 12 10 2 10 5 2 5 13 1 5 10 9 11 9 12 3 3 8 8 7 14 10 1 10 11 3 1 5 2 7 17 8 10 10 10 12 16 6 11 3 7 9 19 13 6 13 10 2 17 12 14 10 13 15 20 5 9 10 3 8 10 12 6 14 17 13 13 8 3 2 3 6 8...
output:
1 2 2 2 2 -1 -1 -1 -1 1 2 -1 -1 2 2 2 2 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1
result:
ok 30 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 94120kb
input:
20 15 30 14 1 14 18 9 18 6 9 2 6 2 10 10 17 11 9 2 16 5 14 10 8 11 20 20 19 3 14 18 7 13 7 15 2 15 12 4 6 13 11 9 13 8 9 15 8 15 7 7 14 14 3 3 10 6 14 9 12 12 1 6 4 2 9 5 14 17 8 14 6 15 10 9 1 4 11 4 1 6 15 18 1 3 1 5 1 9 1 14 4 16 3 12 7 14 2 13 11 7 14 4 4 3 12 1 15 20 15 4 3 14 9 1 13 14 13 4 11...
output:
2 -1 2 2 2 2 -1 1 2 -1 -1 1 -1 2 -1 1 1 -1 2 2 -1 2 2 2 2 -1 -1 2 2 2
result:
ok 30 numbers
Test #13:
score: 0
Accepted
time: 3ms
memory: 87984kb
input:
17 18 30 2 8 16 8 16 3 3 14 14 12 12 10 1 10 11 1 10 6 4 12 4 17 17 9 5 3 5 7 13 4 13 15 18 8 18 10 10 5 7 5 13 7 9 13 11 5 5 15 15 2 6 11 12 7 4 12 17 18 14 12 16 10 3 15 1 13 9 17 16 16 9 12 5 8 13 7 17 8 14 9 4 2 5 7 7 14 14 10 17 16 9 6 14 17 9 8 16 7 16 5 8 7 14 5 6 5 7 1 14 16 14 3 16 15 9 18 ...
output:
-1 -1 2 -1 -1 2 -1 2 1 -1 2 -1 2 2 -1 -1 1 -1 2 2 -1 -1 2 2 -1 2 2 1 -1 -1
result:
ok 30 numbers
Test #14:
score: 0
Accepted
time: 3ms
memory: 98096kb
input:
16 16 30 5 14 14 8 8 13 13 6 6 12 12 2 9 2 6 15 11 13 2 3 8 4 4 10 16 8 7 13 7 1 7 8 8 4 12 4 14 12 14 3 16 3 1 16 14 13 16 15 13 2 11 2 12 9 12 5 10 5 6 12 12 4 8 3 5 8 12 9 4 7 12 14 3 1 15 6 8 9 14 10 13 1 4 11 7 2 3 5 3 14 11 4 2 12 2 12 9 6 1 5 4 4 5 5 14 16 9 5 14 10 5 12 6 15 4 10 16 3 5 16 1...
output:
1 2 1 -1 2 2 -1 -1 0 2 -1 2 -1 -1 2 -1 -1 -1 1 2 -1 1 -1 -1 1 -1 2 2 -1 2
result:
ok 30 numbers
Test #15:
score: 0
Accepted
time: 0ms
memory: 87980kb
input:
18 14 30 8 15 15 18 18 16 13 16 13 7 7 11 3 16 3 12 12 5 1 16 9 1 1 6 7 17 3 4 14 16 10 14 10 2 8 12 14 8 14 7 7 9 9 10 10 2 13 2 11 9 5 11 5 6 10 1 3 2 10 4 6 9 13 12 7 13 10 2 1 12 1 14 15 3 10 11 13 6 6 6 10 2 8 4 3 12 4 12 11 2 14 5 4 1 15 14 17 12 15 6 16 1 3 13 3 9 4 13 4 13 17 10 1 13 4 14 3 ...
output:
-1 -1 2 1 -1 -1 -1 1 1 2 2 2 -1 2 2 -1 2 -1 2 2 1 2 -1 -1 -1 1 -1 2 -1 -1
result:
ok 30 numbers
Test #16:
score: 0
Accepted
time: 3ms
memory: 87928kb
input:
18 15 30 6 4 6 11 11 12 18 12 18 9 16 9 16 3 12 14 14 10 1 12 6 2 1 17 8 12 8 15 5 15 13 8 12 7 3 9 12 9 12 1 1 8 8 2 2 14 11 14 6 11 5 2 8 13 10 13 13 7 4 7 15 12 3 3 13 5 15 9 2 7 4 9 7 3 3 11 15 12 1 5 8 15 2 5 14 4 18 6 5 8 15 3 7 15 9 1 17 3 1 13 12 14 5 8 8 5 14 6 11 12 5 14 11 5 12 4 11 14 13...
output:
1 1 -1 -1 -1 -1 1 1 -1 2 1 2 2 2 -1 -1 -1 2 -1 -1 1 -1 2 1 -1 2 -1 -1 -1 -1
result:
ok 30 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 100268kb
input:
40 21 50 27 28 27 15 3 15 10 3 22 10 17 22 2 17 2 18 35 18 35 12 12 16 16 40 5 40 5 37 37 9 11 9 7 11 7 32 21 32 14 21 14 4 16 26 26 1 34 1 21 36 9 29 29 33 33 30 25 30 12 6 6 31 31 13 13 19 23 2 23 20 8 20 8 38 38 24 39 37 3 2 3 4 4 20 1 20 12 1 8 12 21 8 15 21 5 15 5 19 19 7 12 9 11 9 11 14 12 6 6...
output:
2 -1 2 -1 1 -1 1 2 2 -1 2 2 1 -1 2 2 -1 -1 1 -1 -1 -1 2 -1 -1 2 -1 2 -1 3 2 -1 2 -1 2 2 2 -1 2 -1 3 2 -1 2 -1 -1 2 2 -1 2
result:
ok 50 numbers
Test #18:
score: 0
Accepted
time: 3ms
memory: 100208kb
input:
30 22 50 30 18 29 18 29 24 24 27 27 3 3 23 5 23 4 5 21 4 26 21 13 26 28 5 20 28 3 11 12 11 22 12 3 1 1 8 8 14 14 17 7 17 25 4 16 25 9 16 18 15 2 3 2 10 3 19 19 6 11 7 7 9 9 20 8 20 8 10 10 16 17 16 17 12 15 12 21 15 21 2 18 2 18 22 6 22 16 4 4 13 19 15 14 19 3 14 3 1 1 5 18 18 21 10 8 4 7 12 18 12 8...
output:
-1 1 2 2 -1 -1 1 2 -1 -1 -1 -1 2 2 2 2 -1 2 -1 -1 -1 -1 -1 2 -1 2 2 -1 2 -1 -1 2 -1 -1 -1 2 -1 2 1 1 1 -1 -1 2 2 -1 2 -1 2 -1
result:
ok 50 numbers
Test #19:
score: 0
Accepted
time: 0ms
memory: 100268kb
input:
70 40 90 10 23 67 23 11 67 11 20 45 20 45 14 14 57 57 51 59 51 59 70 70 56 62 11 62 69 28 69 59 54 45 8 35 57 35 52 2 52 6 2 53 20 53 40 53 60 60 41 41 4 11 31 31 9 9 68 32 20 14 49 8 13 11 3 39 49 48 39 48 1 32 19 58 45 66 58 66 34 34 21 8 17 14 5 50 20 37 19 20 44 32 27 58 24 20 33 33 38 18 38 33 ...
output:
1 -1 -1 2 2 -1 2 -1 -1 -1 2 -1 1 -1 1 2 2 2 -1 2 -1 -1 -1 -1 -1 2 2 2 2 1 -1 -1 1 -1 1 2 2 2 -1 2 2 -1 -1 -1 1 2 2 -1 2 -1 -1 2 -1 2 -1 2 -1 2 -1 -1 2 -1 2 2 -1 2 1 2 -1 -1 1 2 1 2 -1 1 -1 2 2 -1 2 1 1 -1 -1 2 1 2 -1 -1
result:
ok 90 numbers
Test #20:
score: 0
Accepted
time: 3ms
memory: 106352kb
input:
70 50 90 45 67 45 5 56 5 45 65 5 53 45 55 5 51 45 19 5 9 5 42 52 45 45 38 5 3 5 54 10 5 5 15 45 6 45 31 26 5 5 33 16 5 18 45 5 37 4 5 25 5 45 43 60 5 59 45 8 5 45 21 39 45 32 45 69 5 11 45 13 45 45 44 5 48 45 17 28 5 5 34 5 62 45 57 45 50 5 64 5 1 5 46 45 66 45 2 45 68 27 45 45 7 29 5 45 49 45 30 63...
output:
1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 1 1 -1 1 1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 -1 -1 1 1 -1 1 -1 1 -1 1 1 1 -1 -1 1 1 -1 1 -1 1 -1 1 -1 -1 -1 1 -1 1 -1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 1 -1 1 1 1 -1 1
result:
ok 90 numbers
Test #21:
score: 0
Accepted
time: 0ms
memory: 100124kb
input:
79 81 90 51 64 42 64 70 42 3 70 34 42 42 7 7 74 64 37 64 49 2 42 43 2 42 41 41 36 13 42 64 61 6 41 16 41 42 58 41 31 13 59 42 66 66 62 56 7 13 26 18 64 21 41 57 13 13 72 9 70 66 23 2 60 35 2 13 65 54 42 54 48 42 76 77 58 64 30 10 41 2 33 70 14 64 53 2 15 8 64 13 5 41 12 24 58 1 7 64 69 42 38 63 38 2...
output:
2 1 -1 2 1 2 2 2 2 -1 -1 1 -1 2 -1 2 -1 -1 1 2 2 2 2 -1 1 -1 -1 2 -1 -1 -1 2 -1 2 2 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 2 1 2 -1 2 -1 -1 -1 2 2 2 -1 2 1 2 -1 -1 -1 1 -1 -1 -1 -1 2 2 -1 2 2 1 -1 -1 2 1 1 -1 1 -1 2 2 -1 -1 -1
result:
ok 90 numbers
Test #22:
score: 0
Accepted
time: 0ms
memory: 98176kb
input:
79 81 90 58 9 58 7 56 7 58 4 33 7 58 25 58 38 73 7 7 13 23 58 64 58 41 7 7 15 7 66 7 21 70 58 59 7 58 65 7 31 46 58 1 7 8 58 19 58 77 7 58 69 34 7 58 47 58 75 58 54 7 60 58 16 7 29 37 7 79 58 68 58 58 48 7 18 10 7 42 7 76 58 58 24 53 58 72 58 58 17 7 67 3 7 63 7 58 49 58 45 58 32 58 57 58 11 7 30 58...
output:
2 1 1 -1 -1 2 2 -1 1 -1 1 1 2 2 -1 -1 -1 -1 -1 1 -1 2 -1 1 2 1 2 -1 -1 -1 1 -1 -1 1 -1 -1 -1 2 1 1 1 2 2 -1 2 2 1 -1 2 2 -1 2 1 -1 1 -1 2 -1 -1 -1 -1 2 1 -1 2 -1 2 1 -1 2 1 -1 -1 1 2 2 -1 -1 -1 -1 1 2 -1 2 1 -1 -1 2 -1 2
result:
ok 90 numbers
Test #23:
score: 0
Accepted
time: 0ms
memory: 96056kb
input:
79 81 99 49 71 76 49 76 41 72 41 72 75 1 75 5 1 50 5 50 46 46 66 1 47 47 57 1 74 75 35 60 35 60 10 44 10 44 36 27 35 4 27 4 16 16 73 47 12 12 29 67 29 41 69 14 69 14 54 1 39 39 61 59 61 34 59 30 75 30 18 18 17 31 17 31 32 41 65 75 28 28 15 15 19 19 25 78 35 3 78 68 74 26 68 45 35 45 64 63 64 63 22 6...
output:
4 3 -1 -1 -1 1 2 3 -1 2 3 3 2 -1 2 -1 3 3 -1 3 2 -1 -1 2 4 -1 -1 3 1 2 2 2 2 3 -1 -1 3 2 -1 2 3 -1 3 -1 3 -1 3 -1 3 2 2 -1 3 -1 2 -1 2 -1 -1 3 -1 2 -1 3 1 3 2 -1 -1 2 2 1 2 2 3 3 -1 -1 -1 2 2 2 2 2 4 -1 2 -1 -1 -1 -1 -1 3 -1 -1 -1 4 -1 3
result:
ok 99 numbers
Test #24:
score: 0
Accepted
time: 4ms
memory: 106356kb
input:
79 81 99 23 53 19 53 36 19 35 36 57 35 1 57 1 20 20 40 11 40 26 11 48 26 35 55 20 59 68 59 68 2 57 69 69 12 46 12 54 57 54 52 1 9 47 9 62 47 62 15 15 34 40 73 73 13 13 27 73 41 73 49 16 54 16 70 70 50 47 39 28 1 77 28 38 77 16 64 64 43 43 44 16 75 75 37 67 53 79 35 60 79 60 72 30 77 30 29 19 6 14 57...
output:
-1 -1 2 2 -1 2 2 1 -1 -1 2 -1 -1 1 -1 2 2 -1 2 2 2 2 1 2 1 -1 -1 2 2 -1 -1 2 2 -1 -1 -1 2 -1 2 -1 2 -1 1 2 -1 -1 1 1 -1 -1 -1 2 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 2 -1 -1 -1 -1 2 -1 -1 -1 -1 1 2 -1 -1 2 2 -1 -1 2 -1 -1 -1 -1 2 2 -1 -1 -1 2 -1 -1 2 -1 2
result:
ok 99 numbers
Test #25:
score: 0
Accepted
time: 0ms
memory: 87880kb
input:
90 89 99 48 81 85 48 85 87 87 8 8 68 53 68 83 53 65 83 79 65 79 43 43 58 67 58 67 82 33 82 33 64 5 64 10 5 14 10 79 88 35 88 78 35 57 78 61 57 44 61 44 32 12 32 18 12 1 8 34 1 35 26 6 26 13 6 77 13 55 77 40 55 59 79 28 59 90 28 29 90 15 29 8 54 22 67 3 22 3 51 51 62 4 62 71 88 46 71 46 45 30 45 41 3...
output:
2 2 -1 -1 2 -1 -1 2 2 2 2 2 -1 -1 2 -1 2 2 -1 1 2 -1 2 -1 2 2 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 2 2 -1 2 -1 -1 2 2 -1 2 -1 1 -1 -1 -1 -1 2 2 2 -1 -1 -1 -1 2 1 -1 -1 -1 2 -1 -1 2 -1 2 -1 -1 2 2 -1 -1 -1 -1 2 -1 -1 2 -1 2 2 2 2 2 -1 2 2 2 2 -1 -1
result:
ok 99 numbers
Test #26:
score: 0
Accepted
time: 3ms
memory: 108496kb
input:
1000 2000 1000 55 910 869 55 548 869 155 548 155 72 72 556 556 558 558 1000 432 1000 338 432 676 338 669 676 669 52 52 279 874 279 77 874 367 77 367 625 611 625 611 549 812 549 333 812 114 333 114 400 400 420 731 420 731 898 898 372 372 127 318 127 318 33 936 33 936 859 198 859 198 663 663 46 596 46...
output:
4 -1 -1 7 -1 9 -1 -1 4 5 -1 8 11 10 6 14 7 -1 -1 3 -1 5 -1 8 6 -1 -1 4 4 -1 -1 9 7 5 -1 -1 -1 -1 -1 -1 -1 -1 8 -1 -1 -1 -1 8 -1 11 -1 -1 4 9 3 7 -1 10 -1 3 7 6 -1 6 -1 5 8 -1 -1 8 -1 7 -1 -1 5 -1 -1 9 -1 -1 12 -1 8 9 12 -1 9 -1 2 -1 -1 6 2 7 13 5 -1 10 6 11 -1 -1 11 -1 -1 8 4 -1 10 -1 -1 5 -1 -1 2 -...
result:
ok 1000 numbers
Test #27:
score: 0
Accepted
time: 0ms
memory: 116736kb
input:
4001 2000 2000 1288 2875 2703 1288 2703 65 1453 65 1453 1733 1733 580 580 22 22 1056 1568 1056 1568 2458 2458 2935 2935 197 197 2140 3941 2140 3399 3941 3399 3338 1934 3338 1934 481 1484 481 554 1484 554 708 1629 708 1216 1629 3785 1216 3785 3948 3948 1468 101 1468 1192 101 1143 1192 2608 1143 2608 ...
output:
5 -1 7 -1 7 -1 -1 10 -1 6 -1 2 13 3 3 -1 -1 7 5 -1 11 6 -1 -1 8 -1 -1 -1 2 5 -1 7 7 -1 11 -1 5 6 -1 -1 5 8 -1 9 11 -1 -1 -1 4 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 5 7 -1 3 -1 5 -1 8 -1 5 -1 4 -1 9 -1 -1 6 -1 10 -1 -1 -1 6 7 -1 -1 4 -1 4 -1 -1 5 -1 -1 6 -1 5 4 -1 -1 -1 4 -1 9 4 4 -1 -1 -1 5 -1 ...
result:
ok 2000 numbers
Test #28:
score: -100
Wrong Answer
time: 7ms
memory: 117068kb
input:
9001 5000 5000 6459 5917 4454 5917 457 4454 457 5629 3359 5629 3359 2940 2940 3531 3531 8220 179 8220 179 8764 2671 8764 2671 5043 5043 3508 3508 2688 2688 1240 1240 3114 5296 3114 7431 5296 8727 7431 1696 8727 7040 1696 7040 8364 8364 6921 6921 7150 7150 2063 4749 2063 4749 6142 6142 5847 5847 7101...
output:
2 -1 -1 2 2 -1 3 -1 3 -1 4 -1 -1 -1 2 -1 -1 3 -1 -1 -1 2 4 -1 -1 -1 -1 3 3 4 -1 3 -1 -1 3 -1 2 2 2 -1 -1 4 3 2 -1 3 2 3 -1 4 -1 2 -1 -1 3 -1 3 2 -1 -1 3 -1 3 -1 -1 -1 -1 -1 3 -1 3 4 -1 -1 -1 2 -1 -1 -1 -1 -1 4 4 -1 -1 4 2 4 -1 -1 2 2 -1 -1 -1 -1 -1 3 -1 2 3 3 -1 3 3 2 -1 -1 3 4 -1 -1 3 2 4 3 2 2 2 2...
result:
wrong answer 192nd numbers differ - expected: '4', found: '3'