QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#562542 | #9295. Treeshop | zjy0001 | WA | 8ms | 100400kb | C++17 | 7.9kb | 2024-09-13 18:25:14 | 2024-09-13 18:25:14 |
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];
pair<int,int>dp[N];
int sz[N],son[N],d[N],f[N],top[N],dL[N],dR[N],bl[N],rk[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){
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].first=u;
for(auto v:G[u])if(v!=fa){
Dp1(v,u);
auto [a,b]=dp[u];auto [c,d]=dp[v];
if(c&&(!a||dist(a,u)<dist(c,u)))swap(a,c);
if(d&&(!a||dist(a,u)<dist(d,u)))swap(a,d);
if(c&&(!b||dist(b,u)<dist(c,u)))swap(b,c);
if(d&&(!b||dist(b,u)<dist(d,u)))swap(b,d);
if(d&&(!c||dist(c,u)<dist(d,u)))swap(c,d);
dp[u].first=a;
if(b&&bl[a]!=bl[b])dp[u].second=b;
else if(c&&bl[a]!=bl[c])dp[u].second=c;
else if(d&&bl[a]!=bl[d])dp[u].second=d;
}
}
inline void Dp2(int u,int fa){
for(auto v:G[u])if(v!=fa){
auto [a,b]=dp[u];auto [c,d]=dp[v];
if(c&&(!a||dist(a,v)<dist(c,v)))swap(a,c);
if(d&&(!a||dist(a,v)<dist(d,v)))swap(a,d);
if(c&&(!b||dist(b,v)<dist(c,v)))swap(b,c);
if(d&&(!b||dist(b,v)<dist(d,v)))swap(b,d);
if(d&&(!c||dist(c,v)<dist(d,v)))swap(c,d);
dp[v].first=a;
if(b&&bl[a]!=bl[b])dp[v].second=b;
else if(c&&bl[a]!=bl[c])dp[v].second=c;
else if(d&&bl[a]!=bl[d])dp[v].second=d;
Dp2(v,u);
}
}
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)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;
const auto [a,b]=dp[u];const auto [c,d]=dp[v];
int sa=max(dist(u,a)+H.solve(a,v),H.solve(u,c)+dist(c,v)),sb=T.solve(u,v);
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;
}
/*
20 15 1
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
9 1 14 4
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 75700kb
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: 45052kb
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: 71764kb
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: 83976kb
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: 73716kb
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: 4ms
memory: 45064kb
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: 0ms
memory: 44972kb
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: 3ms
memory: 45044kb
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: 0ms
memory: 75724kb
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: 73788kb
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: 0ms
memory: 75704kb
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: 79860kb
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: 0ms
memory: 77904kb
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: 0ms
memory: 75792kb
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: 3ms
memory: 79800kb
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: 0ms
memory: 75704kb
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: 79864kb
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: 7ms
memory: 79856kb
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: 83984kb
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: 88056kb
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: 4ms
memory: 84032kb
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: 86024kb
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: 4ms
memory: 85972kb
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: 84052kb
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: 4ms
memory: 86040kb
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: -100
Wrong Answer
time: 8ms
memory: 100400kb
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:
wrong answer 240th numbers differ - expected: '11', found: '12'