QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#449031 | #7772. 意念力 | kkkgjyismine4 | 100 ✓ | 2780ms | 114952kb | C++23 | 6.6kb | 2024-06-20 16:15:46 | 2024-06-20 16:15:48 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define vi vector<ll>
#define pb push_back
using namespace std;
const int maxn=4e5;
int N,M;ll K;
ll X[maxn+5],Res[maxn+5];
const ll mod=998244353;
void add(ll &x,const ll y){if((x+=y)>=mod)x-=mod;}
void del(ll &x,const ll y){if((x+=(mod-y))>=mod)x-=mod;}
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1ll)res=res*a%mod;
a=a*a%mod;b>>=1;
}return res;
}
namespace Poly{
ll f[2000005],g[2000005],A[2000005],B[2000005],C[2000005];
int L,limit,r[2000005];
ll Now[2000005];
void ntt(int nn,ll *a,int op){
limit=1,L=0;while(limit<nn)limit<<=1,++L;
for(int i=0;i<limit;++i)r[i]=((r[i>>1]>>1)|((i&1)<<L-1));
for(int i=0;i<limit;++i)if(i<r[i])swap(a[i],a[r[i]]);
ll G=(op==1?3ll:332748118);
for(int mid=1;mid<limit;mid<<=1){
ll Wn=qpow(G,(mod-1)/(mid<<1));Now[0]=1;
for(int i=1;i<=mid;++i)Now[i]=Now[i-1]*Wn%mod;
for(int j=0;j<limit;j+=(mid<<1)){
for(int k=0;k<mid;++k){
ll x=a[j+k],y=a[j+k+mid]*Now[k]%mod;
add(a[j+k],y);a[j+k+mid]=((x<y)?(x+mod-y):(x-y));
}
}
}
if(op<0){ll inv=qpow(limit,mod-2);for(int i=0;i<limit;++i)a[i]=a[i]*inv%mod;}
}
void getinv(int n,ll *a,ll *b){
int m=n,now=4*(n+m);for(int i=0;i<=now;++i)g[i]=0,f[i]=a[i];
int len=1;g[0]=qpow(f[0],mod-2);
while(len<=n){
int nn=2*len;
for(int i=0;i<(len<<2);++i)A[i]=B[i]=0;
for(int i=0;i<(len<<1);++i)A[i]=f[i],B[i]=g[i];ntt(nn*2,A,1),ntt(nn*2,B,1);
for(int i=0;i<(len<<2);++i)C[i]=A[i]*B[i]%mod*B[i]%mod;ntt(nn*2,C,-1);
for(int i=0;i<2*len;++i)C[i]=(2ll*g[i]+mod-C[i])%mod;
for(int i=0;i<2*len;++i)g[i]=C[i];len<<=1;
}
for(int i=0;i<=m;++i)b[i]=g[i];
}
ll fa[1000005],fb[1000005],d[1000005];
void Div(int n,int m,ll *a,ll *b,ll *c){
for(int i=0;i<=(n<<2);++i)fa[i]=fb[i]=0;
for(int i=0;i<=n;++i)fa[i]=a[i];
for(int i=0;i<=m;++i)fb[i]=b[i];
reverse(fa,fa+n+1);reverse(fb,fb+m+1);int now=n-m;
for(int i=now+1;i<=n;++i)fa[i]=0;
for(int i=now+1;i<=m;++i)fb[i]=0;
getinv(now,fb,fb);
ntt(2*now+1,fa,1),ntt(2*now+1,fb,1);
for(int i=0;i<=(now+1<<2);++i)fa[i]=fa[i]*fb[i]%mod;
ntt(2*now+1,fa,-1);
for(int i=0;i<=now;++i)d[i]=fa[now-i];
for(int i=0;i<=(n<<1);++i)fa[i]=fb[i]=0;
for(int i=0;i<=m;++i)fa[i]=b[i];
for(int i=0;i<=now;++i)fb[i]=d[i];
ntt(n+1,fa,1),ntt(n+1,fb,1);
for(int i=0;i<=(n+1<<1);++i)fa[i]=fa[i]*fb[i]%mod;
ntt(n+1,fa,-1);
for(int i=0;i<=n;++i)fa[i]=(mod+a[i]-fa[i])%mod;
for(int i=0;i<m;++i)c[i]=fa[i];
}
ll fc[1000005],fd[1000005],fe[1000005];
vi mul(vi &a,vi &b){
int len=(int)a.size()+(int)b.size()-1;
for(int i=0;i<(len<<1);++i)fc[i]=fd[i]=0;
for(int i=0;i<a.size();++i)fc[i]=a[i];
for(int i=0;i<b.size();++i)fd[i]=b[i];
ntt(len,fc,1),ntt(len,fd,1);
for(int i=0;i<(len<<1);++i)fc[i]=fc[i]*fd[i]%mod;ntt(len,fc,-1);
vi ans;ans.resize(len);
for(int i=0;i<len;++i)ans[i]=fc[i];
return ans;
}
int tot;ll Nowx[800005];
const int S=150;
vi vec[800005];
void Mod(vi &a,vi &b){
int n1=(int)a.size()-1,n2=(int)b.size()-1;n1=max(n1,n2);
for(int i=0;i<=n1;++i)fc[i]=0;for(int i=0;i<=n2;++i)fd[i]=0;
for(int i=0;i<a.size();++i)fc[i]=a[i];for(int i=0;i<b.size();++i)fd[i]=b[i];
Div(n1,n2,fc,fd,fe);a.clear();a.resize(n2);for(int i=0;i<n2;++i)a[i]=fe[i];
}
void init(int p,int l,int r){
if(l==r){vec[p].resize(2);del(vec[p][0],X[l]);add(vec[p][1],1);return;}
int mid=l+r>>1;init(p<<1,l,mid),init(p<<1|1,mid+1,r);vec[p]=mul(vec[p<<1],vec[p<<1|1]);
}
void solve(int p,int l,int r,vi Now){
if(r-l+1<=S){for(int i=l;i<=r;++i){ll pw=1;for(int j=0;j<Now.size();++j)Res[i]=(Res[i]+Now[j]*pw)%mod,pw=pw*1ll*X[i]%mod;}return;}
int mid=l+r>>1;Mod(Now,vec[p]);
solve(p<<1,l,mid,Now),solve(p<<1|1,mid+1,r,Now);
}
}
#define pii pair<int,ll>
#define fi first
#define se second
#define mp make_pair
ll dis[100005];
int id[100005],ct[100050],sz[100050],mx[100050],rt,mark[100005];
vector<pii>road[100005];
void find(int u,int fa,int act){
sz[u]=1,mx[u]=0;
for(auto V:road[u]){
int v=V.fi;
if(mark[v]||v==fa)continue;
find(v,u,act),sz[u]+=sz[v],mx[u]=max(mx[u],sz[v]);
}mx[u]=max(mx[u],act-sz[u]);
if(rt==-1||mx[rt]>mx[u])rt=u;
}
void getdis(int u,int fa){
sz[u]=1;
for(auto V:road[u]){
int v=V.fi;
if(v==fa||mark[v])continue;
dis[v]=dis[u]+V.se,getdis(v,u),sz[u]+=sz[v];
}
}
struct Node{ll d;int u;}a[100005],b[100050];
bool operator<(Node a,Node b){return a.d<b.d;}
int tt,c[100005];
void add(int p,int o){for(int i=p;i<=N;i+=(i&-i))c[i]+=o;}
int qry(int p){
int ans=0;
for(int i=p;i;i&=(i-1))ans+=c[i];
return ans;
}
void Ins(int u,int fa){
a[++tt]=Node{K-dis[u],u},b[tt]=Node{dis[u],id[u]};
for(auto v:road[u])if(!mark[v.fi]&&v.fi!=fa)Ins(v.fi,u);
}
void calc(int o){
sort(a+1,a+tt+1),sort(b+1,b+tt+1);
memset(c,0,sizeof(c));
int now=1;
for(int i=1;i<=tt;++i){
while(now<=tt&&b[now].d<=a[i].d)add(b[now++].u,1);
ct[a[i].u]+=o*qry(id[a[i].u]-1);
}
for(int i=1;i<now;++i)add(b[i].u,-1);
}
void solve(int u,int G){
rt=-1,find(u,-1,G),u=rt;
dis[u]=0,getdis(u,-1),mark[u]=1;vector<pii>vec;tt=0;a[++tt]=Node{K,u},b[tt]=Node{0,id[u]};
for(auto v:road[u])if(!mark[v.fi])vec.pb(mp(v.fi,sz[v.fi])),Ins(v.fi,u);
calc(1);
for(auto v:vec)tt=0,Ins(v.fi,u),calc(-1);
for(auto v:vec)solve(v.fi,v.se);
}
queue<int>q;
ll fac[100005],ifac[100005],f[100005],g[100005];
vi Calc(int l,int r){
if(l==r){
vi now;now.resize(2);
now[1]=1,now[0]=mod-ct[l];
return now;
}
int mid=l+r>>1;
vi lf=Calc(l,mid),rg=Calc(mid+1,r);
return Poly::mul(lf,rg);
}
ll C(int n,int m){
return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
Node p[100005];
int main(){
scanf("%d%lld",&N,&K);--K;
for(int i=1;i<N;++i){
int u,v;ll w;
scanf("%d%d%lld",&u,&v,&w);
road[u].pb(make_pair(v,w));
road[v].pb(make_pair(u,w));
}
q.push(1);int tt=0;
getdis(1,0);
for(int i=1;i<=N;++i)p[i].d=dis[i],p[i].u=i;
sort(p+1,p+N+1);
for(int i=1;i<=N;++i)id[p[i].u]=i;
solve(1,N);int mx=0;fac[0]=ifac[0]=1;M=N;
for(int i=1;i<=N;++i)mx=max(mx,ct[i]),fac[i]=1ll*i*fac[i-1]%mod,ifac[i]=qpow(fac[i],mod-2),X[i]=i;
Poly::init(1,1,M),Poly::solve(1,1,M,Calc(1,N));
for(int i=1;i<=N;++i)f[i]=Res[i],f[i]=((i>=mx)?f[i]:0ll);
vi a,b,c;a.resize(N+1),b.resize(N+1);
for(int i=1;i<=N;++i)a[i]=f[i]*ifac[i]%mod;
for(int i=0;i<=N;++i){
if(i&1)b[i]=mod-ifac[i];
else b[i]=ifac[i];
}
c=Poly::mul(a,b);
for(int i=1;i<=N;++i)printf("%lld ",c[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 22576kb
input:
10 586964961 10 4 500997470 4 5 361413298 5 3 239036149 5 6 187680375 3 1 199761661 1 2 459686305 6 7 8390746 7 8 59889425 7 9 419949781
output:
0 0 0 0 192 708 636 203 25 1
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 22564kb
input:
10 496325758 3 10 66740689 10 7 456797411 7 9 33319567 9 8 23850338 7 4 698698151 9 6 85638167 4 1 239701723 6 5 11453081 1 2 27039301
output:
0 0 0 0 720 1680 1110 282 29 1
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 22600kb
input:
10 206036637 1 4 60775873 1 9 331998567 1 3 106469067 4 10 157533279 3 6 296084755 3 8 488192398 6 7 215556090 6 5 209447883 5 2 1467187
output:
0 0 972 8244 16270 11846 3815 579 40 1
result:
ok 10 numbers
Subtask #2:
score: 15
Accepted
Test #4:
score: 15
Accepted
time: 38ms
memory: 27492kb
input:
2000 4 325 968 1 968 1118 1 325 430 1 325 1693 1 430 676 1 430 199 1 1693 631 1 631 362 1 325 385 1 676 1441 1 199 1087 1 430 1583 1 1118 674 1 968 1690 1 325 1340 1 199 1718 1 1340 987 1 1690 34 1 362 607 1 607 277 1 34 718 1 1583 1804 1 987 498 1 607 1567 1 362 1332 1 1583 1443 1 607 1920 1 430 76...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 34396558 560597970 342257989 111016545 648115845 896789689 629359408 787287175 225051136 369808516 679693851 350349341 87270678 655949285 424883363 48112584 924467409 910138594 952274861 286758842 346948302 140881427 121554860 465126000 481298451 326871880 970926640...
result:
ok 2000 numbers
Test #5:
score: 0
Accepted
time: 44ms
memory: 27208kb
input:
2000 72 1430 1960 1 1960 1174 1 1174 1305 1 1430 696 1 696 58 1 696 1185 1 1430 610 1 1185 1512 1 1430 1358 1 58 388 1 610 1000 1 388 157 1 1185 1966 1 610 890 1 1966 329 1 1185 800 1 1358 1316 1 890 1517 1 388 1708 1 157 1116 1 157 21 1 1517 1612 1 1612 879 1 1708 567 1 1708 1850 1 1316 124 1 567 5...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 2000 numbers
Test #6:
score: 0
Accepted
time: 45ms
memory: 29308kb
input:
2000 99 117 583 1 117 1553 1 1553 301 1 1553 912 1 912 1582 1 912 1045 1 1582 522 1 1045 898 1 1045 385 1 898 1090 1 385 1499 1 1090 1790 1 1499 1347 1 1499 417 1 1347 1465 1 1465 1932 1 417 291 1 1465 345 1 1932 1312 1 345 1027 1 1027 210 1 1312 1180 1 210 588 1 210 1156 1 1156 1901 1 1901 1662 1 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 2000 numbers
Subtask #3:
score: 15
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #7:
score: 15
Accepted
time: 52ms
memory: 33772kb
input:
2000 1451615371 1496 1341 49707670 1341 444 345030850 1496 1007 685475095 444 1909 278749381 1909 1110 3639571 1341 1869 60712733 1869 521 19317650 1007 732 443227891 444 1258 126491905 1496 1004 482872791 1110 1504 31497121 1004 279 30903287 521 1485 375275915 1007 605 72133480 1869 1570 326176977 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 2000 numbers
Test #8:
score: 0
Accepted
time: 44ms
memory: 39648kb
input:
2000 18850124083 950 1232 22289119 1232 1743 201827311 950 852 235698364 1743 430 879933721 950 416 192976076 1743 195 44313799 950 318 36655137 416 1669 371460821 416 1541 46177715 430 1339 66159023 852 1642 517803961 195 358 294138445 1669 671 183145735 195 1096 412001955 318 1549 213915493 1339 1...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 2000 numbers
Test #9:
score: 0
Accepted
time: 42ms
memory: 39632kb
input:
2000 24843324444 1717 1032 273506143 1717 1999 561959269 1999 1982 29071225 1982 1537 8968261 1982 768 2135953 1982 1125 432656466 1537 1291 56651365 1125 302 269030781 302 1842 161254215 302 138 76677902 138 1663 558013730 1842 1384 269534851 1384 1706 317644801 1663 1240 280572041 1706 628 5688469...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 2000 numbers
Subtask #4:
score: 15
Accepted
Test #10:
score: 15
Accepted
time: 2654ms
memory: 109292kb
input:
100000 49999 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #11:
score: 0
Accepted
time: 2663ms
memory: 110688kb
input:
100000 89999 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #12:
score: 0
Accepted
time: 2633ms
memory: 106988kb
input:
100000 9999 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 3...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Subtask #5:
score: 15
Accepted
Dependency #1:
100%
Accepted
Dependency #4:
100%
Accepted
Test #13:
score: 15
Accepted
time: 2657ms
memory: 113388kb
input:
100000 13263852090411 1 2 125807845 2 3 212692191 3 4 239521145 4 5 602330743 5 6 73379737 6 7 385714963 7 8 454319901 8 9 26509162 9 10 623911298 10 11 630961501 11 12 617362129 12 13 57632397 13 14 540398476 14 15 51636311 15 16 142241401 16 17 514331280 17 18 375448890 18 19 92240301 19 20 374139...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #14:
score: 0
Accepted
time: 2652ms
memory: 111200kb
input:
100000 23978785130960 1 2 21127781 2 3 97510471 3 4 272199663 4 5 129512097 5 6 66154591 6 7 39439131 7 8 334112365 8 9 396429697 9 10 506784181 10 11 356004809 11 12 366299987 12 13 56999785 13 14 159675137 14 15 765389623 15 16 84636940 16 17 93087306 17 18 1013893 18 19 107562136 19 20 141823441 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #15:
score: 0
Accepted
time: 2583ms
memory: 107192kb
input:
100000 287323586802 1 2 1 2 3 1 3 4 3 4 5 5 5 6 3 6 7 1 7 8 1 8 9 3 9 10 6 10 11 7 11 12 4 12 13 9 13 14 1 14 15 1 15 16 5 16 17 4 17 18 3 18 19 6 19 20 7 20 21 9 21 22 8 22 23 5 23 24 5 24 25 1 25 26 1 26 27 3 27 28 5 28 29 5 29 30 8 30 31 5 31 32 1 32 33 3 33 34 7 34 35 1 35 36 9 36 37 1 37 38 6 3...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #16:
score: 0
Accepted
time: 2595ms
memory: 107484kb
input:
100000 26778924982 1 2 3 2 3 4 3 4 9 4 5 1 5 6 5 6 7 3 7 8 1 8 9 1 9 10 3 10 11 2 11 12 7 12 13 5 13 14 2 14 15 3 15 16 5 16 17 6 17 18 3 18 19 1 19 20 1 20 21 1 21 22 1 22 23 8 23 24 3 24 25 4 25 26 7 26 27 1 27 28 4 28 29 1 29 30 9 30 31 7 31 32 5 32 33 3 33 34 3 34 35 9 35 36 6 36 37 6 37 38 8 38...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #17:
score: 0
Accepted
time: 2612ms
memory: 114952kb
input:
100000 2706473915 1 2 2 2 3 3 3 4 1 4 5 7 5 6 3 6 7 5 7 8 5 8 9 5 9 10 5 10 11 9 11 12 1 12 13 6 13 14 7 14 15 3 15 16 7 16 17 9 17 18 3 18 19 1 19 20 1 20 21 4 21 22 9 22 23 1 23 24 1 24 25 9 25 26 9 26 27 10 27 28 9 28 29 3 29 30 5 30 31 2 31 32 7 32 33 9 33 34 10 34 35 9 35 36 5 36 37 7 37 38 9 3...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Subtask #6:
score: 15
Accepted
Dependency #2:
100%
Accepted
Dependency #4:
100%
Accepted
Test #18:
score: 15
Accepted
time: 2748ms
memory: 100544kb
input:
100000 9068 69440 52256 1 69440 83089 1 69440 94352 1 52256 91376 1 91376 83238 1 52256 89768 1 91376 33724 1 89768 26830 1 94352 80177 1 91376 9192 1 94352 87232 1 9192 51458 1 83238 98011 1 83238 88887 1 88887 77270 1 87232 45542 1 9192 91166 1 88887 84875 1 98011 48031 1 48031 99586 1 77270 46971...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #19:
score: 0
Accepted
time: 2698ms
memory: 101672kb
input:
100000 492 96232 74188 1 74188 71245 1 96232 86046 1 86046 90417 1 86046 54649 1 96232 24898 1 96232 61964 1 74188 74009 1 90417 91168 1 96232 98784 1 96232 92160 1 74009 82674 1 54649 89765 1 86046 94252 1 24898 77735 1 74009 88030 1 96232 76695 1 91168 88831 1 77735 79528 1 86046 79644 1 54649 157...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #20:
score: 0
Accepted
time: 2763ms
memory: 102952kb
input:
100000 1820 91599 39208 1 91599 26809 1 91599 66606 1 26809 34935 1 34935 98110 1 66606 22131 1 66606 61150 1 26809 63337 1 26809 67353 1 91599 83940 1 67353 93322 1 63337 42679 1 22131 84494 1 34935 99268 1 42679 86821 1 84494 98736 1 83940 74906 1 86821 78948 1 84494 91224 1 83940 99805 1 98736 73...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #21:
score: 0
Accepted
time: 2745ms
memory: 98540kb
input:
100000 16374 85304 59107 1 59107 54182 1 59107 13098 1 59107 59350 1 59107 76509 1 13098 99436 1 59350 82717 1 13098 65060 1 99436 82905 1 59107 85165 1 59107 96174 1 76509 42678 1 96174 9004 1 42678 99806 1 96174 98354 1 99806 94848 1 96174 93361 1 85165 75306 1 75306 60158 1 85165 91353 1 42678 91...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #22:
score: 0
Accepted
time: 2760ms
memory: 98904kb
input:
100000 1106 97539 64391 1 64391 89243 1 89243 99575 1 89243 90429 1 64391 92533 1 99575 95908 1 90429 82932 1 99575 82134 1 90429 77559 1 82134 71262 1 71262 94673 1 82134 83913 1 77559 96727 1 77559 73969 1 94673 92253 1 92253 30844 1 92253 99069 1 92253 72219 1 92253 71509 1 72219 62306 1 99069 96...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Subtask #7:
score: 15
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Dependency #6:
100%
Accepted
Test #23:
score: 15
Accepted
time: 2755ms
memory: 104552kb
input:
100000 2418281403029 84015 45780 401657711 45780 66164 25505611 84015 62142 129669033 84015 82806 516122920 66164 79160 43075265 79160 66797 10379359 84015 86814 264371829 86814 96961 299843523 96961 68022 282612723 86814 87439 145410185 87439 92904 270871465 68022 84252 190033201 62142 77100 361618...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #24:
score: 0
Accepted
time: 2749ms
memory: 108108kb
input:
100000 133760570773 47390 50927 83452083 50927 84773 8324416 47390 70203 4369834 47390 53093 134685646 84773 87805 928955189 70203 84556 181701517 70203 66959 26057920 70203 54335 14162164 70203 85641 115301395 53093 86851 21902641 87805 72716 386860497 85641 6539 14987643 47390 66270 79946641 54335...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #25:
score: 0
Accepted
time: 2775ms
memory: 100596kb
input:
100000 489583943550 72338 90954 145295929 90954 66627 24618331 66627 39912 724025821 90954 62890 403017525 72338 51483 616741217 90954 85308 204481349 66627 54533 138463720 62890 8313 99112461 8313 28614 92766187 85308 53933 258394513 66627 29453 8154497 8313 34865 95146681 8313 74237 131605501 2861...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #26:
score: 0
Accepted
time: 2780ms
memory: 108536kb
input:
100000 4394939857119 80936 96018 68735877 96018 69278 236811532 96018 71682 177309589 80936 29283 444812345 96018 86412 177048351 71682 96455 220533952 69278 97419 628654573 96018 82572 481498862 96455 5634 217619812 29283 94680 101768561 96455 74038 172597286 5634 45836 46902049 94680 62601 1409485...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers
Test #27:
score: 0
Accepted
time: 2776ms
memory: 105232kb
input:
100000 296164092463 93678 15359 535956721 93678 69347 23593821 15359 82120 643418377 82120 95282 410468165 15359 23598 311136775 95282 36578 62110113 95282 91991 497695741 91991 91175 742959469 91175 41797 18250937 36578 90024 255529081 36578 97407 340226305 90024 4280 251217615 90024 84975 15453220...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 numbers