QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#89570 | #5256. Insertions | daydream | AC ✓ | 290ms | 193136kb | C++14 | 6.5kb | 2023-03-20 16:31:13 | 2023-03-20 16:31:17 |
Judging History
answer
#include<bits/stdc++.h>
#define db double
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define LL long long
#define ldb long double
#define pdd pair<db,db>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pii pair<int,int>
#define pip pair<int,pii>
#define ppi pair<pii,int>
#define ppp pair<pii,pii>
#define pss pair<pair<char,char>,pair<char,char>>
#define fr first
#define sc second
#define mp make_pair
#define id(x,y) ((x-1)*m+y)
using namespace std;
const int mxn=4e5+10,mxm=5010,N=1e6,infi=1e9,mod=998244353,inv2=(mod+1)/2,inv3=(mod+1)/3;
const int v1=37,v2=53,M1=323323323,M2=998244353;
const int dx[]={0,1,0,-1},
dy[]={1,0,-1,0};
const db PI=acos(-1),eps=1e-10;
const LL infl=1e18;
int DB_cmp(db x,db y) {if(fabs(x-y)<eps) return 0; if(x<y) return -1; return 1;}
inline void chkmax(LL &x,const LL y) {if(y>x) x=y;}
inline void chkmax(int &x,const int y) {if(y>x) x=y;}
inline void chkmin(LL &x,const LL y) {if(y<x) x=y;}
inline void chkmin(int &x,const int y) {if(y<x) x=y;}
inline void upd(int &x,const int y) {if((x+=y)>=mod) x-=mod;}
inline int Add(const int x,const int y) {if(x+y>=mod) return x+y-mod; return x+y;}
inline LL my_gcd(LL a,LL b) {if(!a||!b) return a|b; for(LL c=a%b;c;a=b,b=c,c=a%b); return b;}
inline int _pow(int k,int i)
{
int t=1;
for(;i;i>>=1,k=1ll*k*k%mod)
if(i&1)
t=1ll*t*k%mod;
return t;
}
inline int _pow(int k,int i,int M)
{
int t=1;
for(;i;i>>=1,k=1ll*k*k%M)
if(i&1)
t=1ll*t*k%M;
return t;
}
struct SAM
{
int tim,siz[mxn],son[mxn],dep[mxn],top[mxn],dfn[mxn];
int tp,nw,ps[mxn],ln[mxn],fa[mxn],trs[mxn][27];
int f[mxn];
int t,h[mxn];
struct Tre
{
int to,nxt;
}e[mxn];
void add(int u,int v) {e[++t]=(Tre){v,h[u]};h[u]=t;}
int build(int u,int c,int i)
{
int v,x=++tp;ps[i]=x;ln[x]=ln[u]+1;
for(;u&&!trs[u][c];trs[u][c]=x,u=fa[u]);
if(!u) fa[x]=1;
else if(ln[v=trs[u][c]]==ln[u]+1) fa[x]=v;
else
{
fa[++tp]=fa[v];ln[tp]=ln[u]+1;fa[x]=fa[v]=tp;
for(int i=0;i<27;++i) trs[tp][i]=trs[v][i];
for(;u&&trs[u][c]==v;trs[u][c]=tp,u=fa[u]);
}
return x;
}
void dfs1(int u)
{
int v;siz[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
dep[v=e[i].to]=dep[u]+1;
dfs1(v);siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int Top)
{
top[u]=Top;dfn[u]=++tim;
if(son[u]) dfs2(son[u],Top);
int v;
for(int i=h[u];i;i=e[i].nxt)
if((v=e[i].to)!=son[u])
dfs2(v,v);
}
void build(char *s,int L)
{
tp=nw=1;
for(int i=L;i;--i) nw=build(nw,s[i]-'a',i);
for(int i=2;i<=tp;++i) add(fa[i],i);
assert(tp<=mxn);
dfs1(1);dfs2(1,1);
}
int lcm(int x,int y)
{
int u=ps[x],v=ps[y];
for(;top[u]!=top[v];u=fa[top[u]])
if(dep[top[u]]<=dep[top[v]])
swap(u,v);
if(dep[u]<dep[v]) return ln[u];
return ln[v];
}
void upd(int x) {f[ps[x]]++;}
void work(int u=1)
{
int v;
for(int i=h[u];i;i=e[i].nxt)
f[v=e[i].to]+=f[u],
work(v);
}
int qry(int x) {return f[ps[x]];}
}S1,S2,S3;
int n,L1,L2,L3,ans1,ans2,ans3,ans4,cnt[mxn],res[mxn];
char s[mxn],t[mxn],p[mxn],S[mxn];
map<pii,int> ex;
vector<pii> Q[mxn];
vector<int> ins[mxn],del[mxn];
struct BIT
{
int n,tr[mxn];
void upd(int i,int v) {for(;i<=n;i+=(i&-i)) tr[i]+=v;}
void upd(int l,int r,int v) {upd(l,v); upd(r+1,-v);}
int qry(int i) {int res=0; for(;i;i-=(i&-i)) res+=tr[i]; return res;}
}T;
LL rd()
{
static LL sl,fh,ch;
sl=0;fh=1;ch=getchar();
while(ch<'0'||'9'<ch) {if(ch=='-') fh=-1; ch=getchar();}
while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=getchar();
return sl*fh;
}
int main()
{
// freopen("data.in","r",stdin);
// for(int TT=rd();TT;--TT)
{
scanf("%s%s%s",s+1,t+1,p+1);
L1=strlen(s+1);L2=strlen(t+1);L3=strlen(p+1);
n=0;
for(int i=1;i<=L1;++i) S[++n]=s[i];
S[++n]='z'+1;
for(int i=1;i<=L3;++i) S[++n]=p[i];
S1.build(S,n);
n=0;
for(int i=1;i<=L3;++i) S[++n]=p[i];
S[++n]='z'+1;
for(int i=1;i<=L1;++i) S[++n]=s[i];
reverse(S+1,S+n+1);
S2.build(S,n);
int x,y;
ex.clear();
x=y=0;
for(int c,i=1;i<L3;++i)
{
c=p[i]-'a'+1;
x=(1ll*x*v1+c)%M1;
y=(1ll*y*v2+c)%M2;
ex[mp(x,y)]=i+1;
}
x=y=0;
for(int c,i=L2,vx=1,vy=1;i;--i,vx=1ll*v1*vx%M1,vy=1ll*v2*vy%M2)
{
c=t[i]-'a'+1;
x=(1ll*vx*c+x)%M1;
y=(1ll*vy*c+y)%M2;
if(ex.count(mp(x,y))) S1.upd(ex[mp(x,y)]+L1+1);
}
ex.clear();
x=y=0;
for(int c,i=L3,vx=1,vy=1;i>1;--i,vx=1ll*v1*vx%M1,vy=1ll*v2*vy%M2)
{
c=p[i]-'a'+1;
x=(1ll*vx*c+x)%M1;
y=(1ll*vy*c+y)%M2;
ex[mp(x,y)]=i-1;
}
x=y=0;
for(int c,i=1;i<=L2;++i)
{
c=t[i]-'a'+1;
x=(1ll*x*v1+c)%M1;
y=(1ll*y*v2+c)%M2;
if(ex.count(mp(x,y))) S2.upd(n-ex[mp(x,y)]+1);
}
S1.work();S2.work();
for(int i=1;i<=L1;++i) cnt[i]=cnt[i-1]+(S1.lcm(i,L1+2)==L3);
// for(int i=1;i<=L1;++i) printf("%d ",S1.lcm(i,L1+2)==L3);puts("");
for(int i=0;i<=L1;++i)
{
res[i]+=cnt[L1]-cnt[i];
if(i-L3+1>=0) res[i]+=cnt[i-L3+1];
res[i]+=S1.qry(i+1)+S2.qry(n-i-L3);
}
if(L3<=L2)
{
n=0;
for(int i=1;i<=L2;++i) S[++n]=t[i];
S[++n]='z'+1;
for(int i=1;i<=L3;++i) S[++n]=p[i];
S3.build(S,n);
int num=0;
for(int i=1;i<=L2;++i) num+=(S3.lcm(i,L2+2)==L3);
for(int i=0;i<=L1;++i) res[i]+=num;
}
else if(L3>=L2+2)
{
T.n=S2.tp;
x=y=0;int vx=1,vy=1;
for(int c,i=1;i<=L2;++i)
{
c=t[i]-'a'+1;
x=(1ll*x*v1+c)%M1;
y=(1ll*y*v2+c)%M2;
vx=1ll*vx*v1%M1;vy=1ll*vy*v2%M2;
}
pii ht=mp(x,y);vx=M1-vx;vy=M2-vy;
x=y=0;
for(int c,i=1;i<=L2;++i)
{
c=p[i]-'a'+1;
x=(1ll*x*v1+c)%M1;
y=(1ll*y*v2+c)%M2;
}
for(int c,i=L2+1;i<L3;++i)
{
c=p[i]-'a'+1;
x=(1ll*x*v1+c)%M1;
y=(1ll*y*v2+c)%M2;
c=p[i-L2]-'a'+1;
x=(1ll*vx*c+x)%M1;
y=(1ll*vy*c+y)%M2;
if(mp(x,y)==ht)
{
int u,v;
u=S1.ps[i+1+L1+1];
v=S2.ps[n-(i-L2)+1];
ins[S1.dfn[u]].pb(v);
del[S1.dfn[u]+S1.siz[u]].pb(v);
}
}
for(int i=1;i<L1;++i) Q[S1.dfn[S1.ps[i+1]]].pb({i,S2.ps[n-i-L3]});
for(int i=1;i<=S1.tp;++i)
{
for(auto u:ins[i]) T.upd(S2.dfn[u],S2.dfn[u]+S2.siz[u]-1,1);
for(auto u:del[i]) T.upd(S2.dfn[u],S2.dfn[u]+S2.siz[u]-1,-1);
for(auto x:Q[i]) res[x.fr]+=T.qry(S2.dfn[x.sc]);
}
}
ans1=-1;
for(int i=0;i<=L1;++i)
{
if(res[i]>ans1) ans1=res[i],ans2=1,ans3=ans4=i;
else if(res[i]==ans1) ans2++,ans4=i;
}
printf("%d %d %d %d\n",ans1,ans2,ans3,ans4);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 34268kb
input:
rrddrrrdd ddrrd rrddrr
output:
2 2 6 7
result:
ok 4 number(s): "2 2 6 7"
Test #2:
score: 0
Accepted
time: 1ms
memory: 33076kb
input:
z zzkkzzkk z
output:
5 2 0 1
result:
ok 4 number(s): "5 2 0 1"
Test #3:
score: 0
Accepted
time: 3ms
memory: 33072kb
input:
wgwwggggw g gggg
output:
2 5 4 8
result:
ok 4 number(s): "2 5 4 8"
Test #4:
score: 0
Accepted
time: 1ms
memory: 32852kb
input:
q uuquu u
output:
4 2 0 1
result:
ok 4 number(s): "4 2 0 1"
Test #5:
score: 0
Accepted
time: 9ms
memory: 31856kb
input:
gpgggpppg pg gpgg
output:
2 1 4 4
result:
ok 4 number(s): "2 1 4 4"
Test #6:
score: 0
Accepted
time: 5ms
memory: 32312kb
input:
p xpxp p
output:
3 2 0 1
result:
ok 4 number(s): "3 2 0 1"
Test #7:
score: 0
Accepted
time: 1ms
memory: 33680kb
input:
aacaacacaa ca caca
output:
2 5 2 9
result:
ok 4 number(s): "2 5 2 9"
Test #8:
score: 0
Accepted
time: 6ms
memory: 31780kb
input:
k kekekkekk k
output:
7 2 0 1
result:
ok 4 number(s): "7 2 0 1"
Test #9:
score: 0
Accepted
time: 4ms
memory: 32736kb
input:
ghhhhg g ghhg
output:
2 1 3 3
result:
ok 4 number(s): "2 1 3 3"
Test #10:
score: 0
Accepted
time: 5ms
memory: 32548kb
input:
b xbb b
output:
3 2 0 1
result:
ok 4 number(s): "3 2 0 1"
Test #11:
score: 0
Accepted
time: 8ms
memory: 31992kb
input:
nddnnndndn dnd ndndn
output:
3 1 5 5
result:
ok 4 number(s): "3 1 5 5"
Test #12:
score: 0
Accepted
time: 1ms
memory: 31848kb
input:
imiimmmm miimi i
output:
6 9 0 8
result:
ok 4 number(s): "6 9 0 8"
Test #13:
score: 0
Accepted
time: 1ms
memory: 31956kb
input:
gzzzzzzzzz zgzzzg gzgggzzz
output:
0 11 0 10
result:
ok 4 number(s): "0 11 0 10"
Test #14:
score: 0
Accepted
time: 1ms
memory: 32828kb
input:
m mmwmwmw wwmww
output:
0 2 0 1
result:
ok 4 number(s): "0 2 0 1"
Test #15:
score: 0
Accepted
time: 6ms
memory: 32244kb
input:
jmmmmjmmj jmjjjmjm mjmmmmjj
output:
0 10 0 9
result:
ok 4 number(s): "0 10 0 9"
Test #16:
score: 0
Accepted
time: 2ms
memory: 33876kb
input:
f ffffwff wffw
output:
0 2 0 1
result:
ok 4 number(s): "0 2 0 1"
Test #17:
score: 0
Accepted
time: 7ms
memory: 32740kb
input:
plpll llplll pppppppl
output:
0 6 0 5
result:
ok 4 number(s): "0 6 0 5"
Test #18:
score: 0
Accepted
time: 1ms
memory: 33380kb
input:
yypppypyy ppyyypppy ypyppypp
output:
0 10 0 9
result:
ok 4 number(s): "0 10 0 9"
Test #19:
score: 0
Accepted
time: 3ms
memory: 33316kb
input:
okkkkkok okokkkoo kookooko
output:
0 9 0 8
result:
ok 4 number(s): "0 9 0 8"
Test #20:
score: 0
Accepted
time: 7ms
memory: 32816kb
input:
ccc cpppp cc
output:
3 1 3 3
result:
ok 4 number(s): "3 1 3 3"
Test #21:
score: 0
Accepted
time: 1ms
memory: 33064kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
631 1000 0 999
result:
ok 4 number(s): "631 1000 0 999"
Test #22:
score: 0
Accepted
time: 12ms
memory: 35312kb
input:
annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #23:
score: 0
Accepted
time: 4ms
memory: 35548kb
input:
atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...
output:
0 1000 0 999
result:
ok 4 number(s): "0 1000 0 999"
Test #24:
score: 0
Accepted
time: 1ms
memory: 33080kb
input:
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
1 413 587 999
result:
ok 4 number(s): "1 413 587 999"
Test #25:
score: 0
Accepted
time: 13ms
memory: 34240kb
input:
rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...
output:
315 2 1 998
result:
ok 4 number(s): "315 2 1 998"
Test #26:
score: 0
Accepted
time: 1ms
memory: 33364kb
input:
huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...
output:
260 1 113 113
result:
ok 4 number(s): "260 1 113 113"
Test #27:
score: 0
Accepted
time: 5ms
memory: 33280kb
input:
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
748 907 0 906
result:
ok 4 number(s): "748 907 0 906"
Test #28:
score: 0
Accepted
time: 3ms
memory: 34516kb
input:
kkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkpkppkkkkkkpkkkkkkkkkkkkkkkpkkkkkkkkkkkppkkpkkkkkkkkkkkpkkpkpkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkpkpkkkkkkkpkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkpkkkkkkpkkkkkkkkkkkkkkkkkkkpkkkpkkkkkpkkkkkkkpkpk...
output:
0 907 0 906
result:
ok 4 number(s): "0 907 0 906"
Test #29:
score: 0
Accepted
time: 4ms
memory: 34560kb
input:
illillliiiiiilliiilliiilliliilililiililiiililililliliililiillilliliiiiiliiillllllllilliiilililiililililliiiliiililiillillliliiiliiliiliililllliiliiililiilllilllllliiliiiillilillllllillllililililliiiiliilliililllllilliliiiiilililiiiillliiillliililllilliiiiiilliilllllllliillllliiiiiiilliiliilllliiliil...
output:
0 907 0 906
result:
ok 4 number(s): "0 907 0 906"
Test #30:
score: 0
Accepted
time: 4ms
memory: 32988kb
input:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
1 702 0 701
result:
ok 4 number(s): "1 702 0 701"
Test #31:
score: 0
Accepted
time: 1ms
memory: 33832kb
input:
mymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymy...
output:
374 454 0 906
result:
ok 4 number(s): "374 454 0 906"
Test #32:
score: 0
Accepted
time: 6ms
memory: 33444kb
input:
kckckckckckckckckckckckckckckckckckckckckckckckccckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckc...
output:
291 370 50 788
result:
ok 4 number(s): "291 370 50 788"
Test #33:
score: 0
Accepted
time: 7ms
memory: 32864kb
input:
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
937 966 0 965
result:
ok 4 number(s): "937 966 0 965"
Test #34:
score: 0
Accepted
time: 4ms
memory: 33268kb
input:
apaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaapapaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaapaaaapapappaaaaaaaapaaappaaaapaapapaaaaaaapaaaappaaapaaaaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaapaaaaaaaapaaaapppaapaaaaaaaaaaaapppaapaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaa...
output:
35 64 600 663
result:
ok 4 number(s): "35 64 600 663"
Test #35:
score: 0
Accepted
time: 9ms
memory: 34736kb
input:
msmmssmmsmmmsmssmmmmmsmmmsmssssssssmmmmssmmsmmsmmmsmssmmmmsssmmsmmmssmssmsmmmsmssmsmmmsmmmsmssmsssmmssssmmmssmmssssmsmsmsmmmsmsmmsmsmssssssssmmmmmmsmmmsssmmmssssssssssmmmmssmsmsmmsmssssssssmmsmmsssmssmmmssssmsssmssmssmsmsmsmsmmsmmssmmsmmsmsmmssmmssmsmssmsssmsmsmsmmmmsmssmmmmsmmssmmmssssmsssssmmssmmm...
output:
0 966 0 965
result:
ok 4 number(s): "0 966 0 965"
Test #36:
score: 0
Accepted
time: 4ms
memory: 33716kb
input:
nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...
output:
1 768 0 767
result:
ok 4 number(s): "1 768 0 767"
Test #37:
score: 0
Accepted
time: 3ms
memory: 33356kb
input:
jrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjr...
output:
468 483 0 964
result:
ok 4 number(s): "468 483 0 964"
Test #38:
score: 0
Accepted
time: 3ms
memory: 33584kb
input:
dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkkkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk...
output:
429 443 80 964
result:
ok 4 number(s): "429 443 80 964"
Test #39:
score: 0
Accepted
time: 133ms
memory: 113000kb
input:
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...
output:
44459 99774 0 99773
result:
ok 4 number(s): "44459 99774 0 99773"
Test #40:
score: 0
Accepted
time: 187ms
memory: 142276kb
input:
annnannnnnnnnnnnnnnnnnnnannnnnnnnnnannnnnnnnnnnnnnannananannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnannnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnaannnnnnnnnnnnnnnnnnnnnannannnnnnnnnnnnannnannnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnaannan...
output:
0 99774 0 99773
result:
ok 4 number(s): "0 99774 0 99773"
Test #41:
score: 0
Accepted
time: 273ms
memory: 161196kb
input:
eyyeeeyyeyyeyeyyeyeeyyyyeeeeeyyyyeeeeyyyyyyyyyyyeeeeeeeeyeyyyeyyeeyyyeeyeeeeyeeyeeeeeeyyyeeyeeyeeeyyeyeyyeyyeyeyyyeyyeeeeeyeyyyyyeyyeyeyeeyyyyyeeyeyeeeyeeeyyyeeyeeyyyeeyyyeeyeyyeeeeyeyeeeyyeeyyeyeyyeeyyeyyyyeeeyyyeyyyeyyeeyeeeeeeyyyeyeyeyeeeeeyeyeyeyyeyeyyyyyyeyeeyeyyyeeeyeeyyeeyyyeyeyeyeyyyyyyeeeey...
output:
0 99774 0 99773
result:
ok 4 number(s): "0 99774 0 99773"
Test #42:
score: 0
Accepted
time: 140ms
memory: 115716kb
input:
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...
output:
1 61041 38733 99773
result:
ok 4 number(s): "1 61041 38733 99773"
Test #43:
score: 0
Accepted
time: 135ms
memory: 127072kb
input:
zqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzq...
output:
22229 2 1 99772
result:
ok 4 number(s): "22229 2 1 99772"
Test #44:
score: 0
Accepted
time: 129ms
memory: 126300kb
input:
babababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...
output:
22229 2 1 99772
result:
ok 4 number(s): "22229 2 1 99772"
Test #45:
score: 0
Accepted
time: 151ms
memory: 103920kb
input:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
85548 90750 0 90749
result:
ok 4 number(s): "85548 90750 0 90749"
Test #46:
score: 0
Accepted
time: 236ms
memory: 132424kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbobbobbbbbobbbobbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbobbbbbbbbbbbobbbbbbbboobbobbbbbbbbbbobbbbbbbbbbbbbbbobbbbobbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbobbbbbbbbbbbbbbbbboobbbbbobbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbbbbbobbbobobbobbbbbbbbbbbbbbbbbbobbbbbbbobbbbbb...
output:
0 90750 0 90749
result:
ok 4 number(s): "0 90750 0 90749"
Test #47:
score: 0
Accepted
time: 289ms
memory: 152160kb
input:
llrlrrlrlrrllrrrrrlrlrlllllrrrrllrllrrllllrrlrlrllllllrrrlrllllllrrrlrrrrlrlrllrrrrrrrrlrlrrrlrrlrlllllrllrllrlrlllrrrrllllllllllrrrllrrlllrlrllrrrlllrrllrrrlllrlrlrlrlrlrllrlrrrrrrlrlrrllrrrrrrllrllrrlrlrlllrrrlrrrlrrrrrrrrrlrlllrlrlrlrlrllllrlrrrrrlllrlllrlrrlrrrlrlrllrrrrlllllllrllrlrlllllrrrrrrr...
output:
0 90750 0 90749
result:
ok 4 number(s): "0 90750 0 90749"
Test #48:
score: 0
Accepted
time: 159ms
memory: 115908kb
input:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
1 71220 19530 90749
result:
ok 4 number(s): "1 71220 19530 90749"
Test #49:
score: 0
Accepted
time: 161ms
memory: 119152kb
input:
qoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqo...
output:
42774 45375 0 90748
result:
ok 4 number(s): "42774 45375 0 90748"
Test #50:
score: 0
Accepted
time: 135ms
memory: 119812kb
input:
xtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxt...
output:
40492 43093 2508 88692
result:
ok 4 number(s): "40492 43093 2508 88692"
Test #51:
score: 0
Accepted
time: 153ms
memory: 124896kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
97181 91251 0 91250
result:
ok 4 number(s): "97181 91251 0 91250"
Test #52:
score: 0
Accepted
time: 225ms
memory: 149892kb
input:
vvvvvvvvvvvvvvvvvvmmvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvmvvvvvvvmvvvvvvmvvmvmvmvmvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvmvmvvvvvvvvvvmmvvvvvvvvvvvvvvvmvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...
output:
6028 98 22809 22906
result:
ok 4 number(s): "6028 98 22809 22906"
Test #53:
score: 0
Accepted
time: 290ms
memory: 193136kb
input:
qxqxqxxxxqxqxqqxqqqxqxxxqxqqxxxxqqqqqxxqqxqqqxxxqxxqqxxqxqqxxxxqxxqxqqqxxqqxxqqxqxxxxxxqxqqqqqxxqxqqxxqxqqxxxxxxqxqxqxqqqqqqxxqqqxqqqqqqxqxxqqqxxxqxxqxqqqxxxxqxxxxqqqxxxxqqxqxqqxxqqqqqxqxxqxxxxqxxxxxqqqxxqqqqxqxqqqxqxxxxxqxxqxqqxqxqxxqqqxqqqqxxxxxqxxqxxqqxqxqxqqqqxqxqxqxxxxqxxqqxqqxqqxxxxxqqxxqxqqqq...
output:
0 91251 0 91250
result:
ok 4 number(s): "0 91251 0 91250"
Test #54:
score: 0
Accepted
time: 145ms
memory: 148976kb
input:
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
1 4772 86479 91250
result:
ok 4 number(s): "1 4772 86479 91250"
Test #55:
score: 0
Accepted
time: 160ms
memory: 162472kb
input:
lglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglg...
output:
48590 45626 0 91250
result:
ok 4 number(s): "48590 45626 0 91250"
Test #56:
score: 0
Accepted
time: 170ms
memory: 154124kb
input:
ibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibib...
output:
22317 19352 36850 75552
result:
ok 4 number(s): "22317 19352 36850 75552"
Test #57:
score: 0
Accepted
time: 3ms
memory: 34500kb
input:
abbababa babbba bbab
output:
2 6 1 7
result:
ok 4 number(s): "2 6 1 7"
Test #58:
score: 0
Accepted
time: 4ms
memory: 34580kb
input:
ababbabaabbabbbabbaabababaaababaabaaababbbbabababbbbaaabbbabbbbaaabbbbbbbbaabaabaabbaaababbbbbabbbba aabaaababaabaabababbbaaabbbbbbaabaabaaabbaaabababbaabbaabbab abbbbaabaa
output:
1 7 43 99
result:
ok 4 number(s): "1 7 43 99"