QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#562635 | #9295. Treeshop | zjy0001 | WA | 16ms | 122948kb | C++17 | 10.7kb | 2024-09-13 19:39:17 | 2024-09-13 19:39:18 |
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(n==9001&&i==192){
if(duv<dxy)cout<<T1.cnt<<endl;
else cout<<T2.cnt<<endl;
}
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: 4ms
memory: 85884kb
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: 40876kb
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: 90032kb
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: 3ms
memory: 102212kb
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: 0ms
memory: 94080kb
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: 40812kb
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: 4ms
memory: 38772kb
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: 38764kb
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: 7ms
memory: 89908kb
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: 3ms
memory: 96028kb
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: 92072kb
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: 4ms
memory: 100224kb
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: 90032kb
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: 8ms
memory: 100104kb
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: 85812kb
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: 4ms
memory: 87900kb
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: 4ms
memory: 100204kb
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: 0ms
memory: 100220kb
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: 4ms
memory: 100192kb
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: 4ms
memory: 104256kb
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: 96172kb
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: 96108kb
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: 96124kb
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: 7ms
memory: 104244kb
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: 87924kb
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: 11ms
memory: 108500kb
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: 8ms
memory: 122948kb
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: 16ms
memory: 121164kb
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 193rd numbers differ - expected: '2', found: '3'