QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#197204 | #7512. Almost Prefix Concatenation | flame | WA | 508ms | 178280kb | C++14 | 2.6kb | 2023-10-02 13:16:06 | 2023-10-02 13:16:08 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
#define LL long long
#define ls (ro<<1)
#define rs ((ro<<1)|1)
#define Mid ((l+r)>>1)
using namespace std;
int const N=1e6+50,mo=998244353;
struct stu1{
LL f,g,w; LL tf,tg,tw;
}t[N*4];
int nex[N],n,m;
char S[N],T[N];
ull P[3]={131,13331,114514},pw[3][N],haS[3][N],haT[3][N];
bool check(int l1,int r1,int l2,int r2){
for(int k=0;k<3;k++){
ull val1=haS[k][r1]-haS[k][l1-1]*pw[k][r1-l1+1];
ull val2=haT[k][r2]-haT[k][l2-1]*pw[k][r1-l1+1];
if(val1!=val2) return 0;
}
// cout<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<' '<<r1-l1<<' '<<r2-l2<<' '<<val1<<' '<<val2<<endl;
return 1;
}
void xg(int ro,int l,int r,int L,int R,stu1 val){
if(L<=l&&r<=R){
LL w1=val.f+val.g*2ll+val.w;
LL w2=val.g+val.w;
t[ro].tf+=w1; t[ro].tg+=w2; t[ro].tw+=val.w;
t[ro].tf%=mo; t[ro].tg%=mo; t[ro].tw%=mo;
return;
}
if(L<=Mid) xg(ls,l,Mid,L,R,val);
if(R>Mid) xg(rs,Mid+1,r,L,R,val);
}
stu1 cx(int ro,int l,int r,int md){
if(l==r){
stu1 t1=t[ro];
return (stu1){(t1.f+t1.tf)%mo,(t1.g+t1.tg)%mo,(t1.w+t1.tw)%mo};
}
stu1 t1,t2=t[ro];
if(md<=Mid) t1=cx(ls,l,Mid,md);
else t1=cx(rs,Mid+1,r,md);
t1.f+=t2.tf; t1.g+=t2.tg; t1.w+=t2.tw;
t1.f%=mo; t1.g%=mo; t1.w%=mo;
return t1;
}
int main(){
scanf("%s%s",S+1,T+1);
n=strlen(S+1);
m=strlen(T+1);
for(int k=0;k<3;k++){
pw[k][0]=1;
for(int i=1;i<=max(n,m);i++) pw[k][i]=pw[k][i-1]*P[k];
for(int i=1;i<=n;i++) haS[k][i]=haS[k][i-1]*P[k]+(S[i]-'a'+1);
for(int i=1;i<=m;i++) haT[k][i]=haT[k][i-1]*P[k]+(T[i]-'a'+1);
}
for(int i=1;i<=n;i++){
int l=i,r=min(n,i+m-1),mid,pos1,pos2;
int n1=min(n,i+m-1);
if(S[i]==T[1]){
while(l+1<r){
mid=(l+r>>1); //1 1
if(check(i,mid,1,mid-i+1)) l=mid;
else r=mid-1;
}
// cout<<l<<' '<<r<<' '<<r-i+1<<endl;
if(check(i,r,1,r-i+1)) pos1=r;
else pos1=l;
pos1=min(pos1+1,min(n,i+m-1));
}
else pos1=i;
// cout<<"qwq"<<pos1<<endl;
int len=pos1-i+1;
pos2=pos1;
if(pos1!=min(n,i+m-1)){
int l1=pos1+1,r1=min(n,i+m-1); //不合法位置的后一个
while(l1+1<r1){
mid=(l1+r1>>1); //len+1: 起点
if(check(pos1+1,mid,len+1,len+mid-(pos1+1)+1)) l1=mid;
else r1=mid-1;
}
if(check(pos1+1,r1,len+1,len+r1-pos1)) pos2=r1;
else if(check(pos1+1,l1,len+1,len+l1-pos1)) pos2=l1;
else pos2=pos1;
}
nex[i]=pos2;
// cout<<nex[i]<<endl;
}
stu1 t1={0,0,1}; xg(1,1,n,1,nex[1],t1);
for(int i=1;i<n;i++){
t1=cx(1,1,n,i);
xg(1,1,n,i+1,nex[i+1],t1);
// cout<<t1.f<<' '<<t1.g<<' '<<t1.w<<endl;
}
t1=cx(1,1,n,n);
printf("%lld",t1.f);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 14116kb
input:
ababaab aba
output:
473
result:
ok 1 number(s): "473"
Test #2:
score: 0
Accepted
time: 0ms
memory: 14156kb
input:
ac ccpc
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 2ms
memory: 14212kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
75038697
result:
ok 1 number(s): "75038697"
Test #4:
score: 0
Accepted
time: 2ms
memory: 14212kb
input:
lvvvllvllvllvllllllllvvvllvlllvvlvlvllvlvvlvvvvlvvllllllvvlvlvvlllvvlvlvllllllvlvvvvvvlllvvvllvlvvvlvvlllvvvvvvlvlllvvvvlvvvvvlvvlvvlllvvllvvllvlvlvlvlvllllvvllvvllvlllvvvllllvvlvvllvvvvlvlvvlvvlllvvvvvvvvlvvlvlllvllvvvvllvvvlvvvvvvlvlllvllllvllllllllvvllllllvlvvlvvvlvllllvllvlvvllllllvlvvvlvlvlvvvl...
output:
538419149
result:
ok 1 number(s): "538419149"
Test #5:
score: 0
Accepted
time: 0ms
memory: 14004kb
input:
fzztyyyfztzzfzyztftyfzyyzzzztyyfzttzttztyzztyyyfyyftyfyfzzffyzffytttzttyzzftyfyfyftyyfzyzffyfyyzztzyyttyfyztfyfzyfzfzyftttfyyfyytzyyzfyyyzztfttzyyytzzffytyzyyyyfzfftftzzztyfftfzfzytftfttytfyzfytzfzztttttzzyztyftzzzfzfzfffttyztzfftfftyfyffztzyffttyyfyfzytytyyttfzzfyyytzzftzyyfftftyytyffzffztfytfyyyty...
output:
867833603
result:
ok 1 number(s): "867833603"
Test #6:
score: 0
Accepted
time: 2ms
memory: 14036kb
input:
xauxlgtqbsianlzjzglalnbtlujfrkfdqgczpmididmtamzeablrbrbjgtsdkzzcfhvcpdawqkrgdsereirlxbizhbsxlcbtgwwshekbhatqonvgupswcowythifpoubxkuoxuuisnzolzwektdcaouxbkhofvdqzmjulmhgqjxwzhgrzmorhqkgekntbzsxgvjtehfbterrhhjhqggzrqiqmcshzwpfoburpyfoehqgtitesyaekhlzcvxzdqmunyrlrhbrjoigdjzpcgptyoiowwnmqrxucxixxydurbdh...
output:
301464023
result:
ok 1 number(s): "301464023"
Test #7:
score: 0
Accepted
time: 3ms
memory: 14688kb
input:
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...
output:
816920406
result:
ok 1 number(s): "816920406"
Test #8:
score: 0
Accepted
time: 0ms
memory: 14524kb
input:
cxccxccccxccxccxcxxxccxxcxcxcxcxxcccxcxccccccxccccxccxcxcxxcxxcxcxxxcxcccxcxxxxxccxxcccxxccxxxccxccxxxxcxxccccxccxxcccxcccxxxccccxcxcxccccxxxxccxxxxxcxxxxxxcxxccxxcxcxcxxxxxcxxccxcxxxcccxcxxxccccccccxxxcccxcxxcxxxxccxxxcccccxcccxccccccxxcccxxcccxxxccxxcxccxcccxxxccxccxxxccxcxxxxccxxcxcxxcxxccxxxcxcx...
output:
206627037
result:
ok 1 number(s): "206627037"
Test #9:
score: 0
Accepted
time: 0ms
memory: 14476kb
input:
vmqvvbbmvmmmqqvqvmmbbvqbqvbmmbqmvvbmmmqvqvbvqqmvbbmmvmvqbvmqqbqvqqvmvmmbqvvbvmvbqmqqbqqqbqqmvvmmbvvvbvvvbmqqvbqbmvvmvqqvbqbvvvqmvvvmvqqmvqbmbvmvmqmmbmqqqbbmvqbqbbqqbmmvmmqqqvvvqqqqqmmvvvvqmvmmmmvmqmqbbvbvvqmmmqbbmvqvmvmqbqbbbmqbqbqmqbqmqbmvvqmmvbmmbvbqqvmmmbbmbbmvmmvbmqmqbbqqbqqbbqmbmmmqbqbmvbmvmmmm...
output:
460659355
result:
ok 1 number(s): "460659355"
Test #10:
score: 0
Accepted
time: 3ms
memory: 14592kb
input:
xthikaxiescbqjzrpgtcpigqjsojlsxsiowkkzsdsgscoolhdtglvpgcoggzqnnjmocvanrogbzqjcmijoukjicadaakehxgjphjgnskjvfneoyaucfadilscsucjgweuzcdfapfnrfffdowxvzkvgqzmtszjldylvehzjlvmhproaehqhuwdoadenqdrqwrlxxfouzqolwbopmkpjshczocnnsxktxozahzwqpwbmvexguvjhbvbjwsdtgaitoqwsfzkwnzgeidkamgcfhzhitfxenunlcsbsesbczvmmbu...
output:
906223232
result:
ok 1 number(s): "906223232"
Test #11:
score: 0
Accepted
time: 35ms
memory: 36580kb
input:
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...
output:
39285513
result:
ok 1 number(s): "39285513"
Test #12:
score: 0
Accepted
time: 48ms
memory: 35720kb
input:
hghggghghhghhgghgggghhghhhgghggghghhhhghghgggghhggggghhgghggghhhghggghghghggghggghgghhhghgggghghghgggghhhhhgghhgghhhghhghhhghhhhhhghghhgggggghghgggghghhghhgghhghhhhhhghgghhghghgggghgggggghghhhhhghhhhhhhgghhggggghhgghhhhhhhhghggggggghhghhghhghhgghhghgghhhhgghghghhhhhghggghhhhhhhgggggghgghghhhhghhgggg...
output:
58618935
result:
ok 1 number(s): "58618935"
Test #13:
score: 0
Accepted
time: 44ms
memory: 34784kb
input:
nnttcybbmnrnsuybrkmkmtumcyuyrrmbtybutunsyrkmunmncmkuknttmmtkymtcybttrmyrtckscttcksbtymtyukbbynnnbukttncmbutscbrytbrutnuyuknmtymckkttrrnsbtrkbnnnkbrccrcyybmnnybbkkbcbbccycsrcytnuucbbyytckrycktsmkymruycksrscytkskscbtbccbrurmumrkbkbttkcynmymbbmbkrksmnusryumsmmyrcsmusumbrkkbmsbyytmmruubskccsusnntcuntrrt...
output:
46252951
result:
ok 1 number(s): "46252951"
Test #14:
score: 0
Accepted
time: 33ms
memory: 33912kb
input:
ittaztseqcdirziayobnnxuzipvteycmgjbupnlxuheulnmzsdeymctprlxvkvzjwrotsauxagyrqcwzuwqyodrqsupwpyrmbwjqlvfdsrocneigxvnjfiseotxmutzwacfutqlmzmxwuqgjugwkafnxvzutgbrweqrdshwneksgxzzinnmbbioqdvbmavukaegvkpwauuoysklelsqhytlikpdpymbwhmbdmrycaiywtwjjqtecwoofyjhbumjtipwyopkuralejvopitpjcdswcvsugimgbrlibrteaqtb...
output:
838361918
result:
ok 1 number(s): "838361918"
Test #15:
score: 0
Accepted
time: 508ms
memory: 176940kb
input:
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...
output:
774442405
result:
ok 1 number(s): "774442405"
Test #16:
score: 0
Accepted
time: 435ms
memory: 171260kb
input:
nnnddndnndnddddndnnddnddnndddndndnnndnndndndnnnddndndnddnnddnndndndnnnndndddndnndndnndddndnnddnndndnnddnnddnddndddnnnndnnndddnndnddnnnddndddnndnnndndndndnddnddnndddndddnnndddnnndnndnndnnnddnnddnndnnndnnnddnnddddnndnnddnndnnnddddnddnnndnnddddddndndnnnnndnnnndddddnddnnndddndnnddndnnnddddnndndnndndndnd...
output:
478212008
result:
ok 1 number(s): "478212008"
Test #17:
score: 0
Accepted
time: 441ms
memory: 154384kb
input:
ievnetxypatirsocqrmgmhfxnkgzrscclietylohbcshjjxfmqhlxvebythkwllhjxwjngxbjeivttdgjttmyqgxsqotxueuvzrslcqpranaucprjmfczshtoqggczmbuwixllhnlcjhrvfixisvqdlxxmevucbvzolweshgvxeocppggthqkljyiszeqkpnybogisosqzdasfqgpuzudnnabwoqtrpxllqkxlbwsexwduvutufncthrmywlsqlccetggdflmgewzvhsmpyznzsxcftkoyfhgmgvliwxbywi...
output:
702291108
result:
ok 1 number(s): "702291108"
Test #18:
score: 0
Accepted
time: 477ms
memory: 178280kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
301945039
result:
ok 1 number(s): "301945039"
Test #19:
score: 0
Accepted
time: 468ms
memory: 172340kb
input:
gggggcgcgggcgccgggcgcccgccccggcccgcggccccggcccccggccgccccccggcccgggcccgggggcccgggggcgggccgcccccccgcgcggggggggggcggggggcggccgcccggggccgccccgcgcgggcggggccgcgcggcggccgggccgccgcggcccgcccggcgccgccgggcgggggcggggccgccgcccccgccccccgggggcgcgcgccggccggcggcggggcgccggcgccccggccgggggccgccccccccgcggcgcggggggcgccc...
output:
602912498
result:
ok 1 number(s): "602912498"
Test #20:
score: 0
Accepted
time: 432ms
memory: 154764kb
input:
zdomsivxdzqlpexdauxxrjvembwqtchcxcpboqwmilagfpnrzyicztptfvdlqehajqoxcqvtoglsusgfioxtwheivlmgapepuoevghzmdadbkkkrdusnvxmansofunrgmppyktkxcottuiolirqlsflpnkghhxngutoovfzluiboooswqknpedyiaspikpveswjqnqitfbynjgiqymkrldekgmkavalduxlscjewmpoctbxjujtxlavpibkyerspcfchiticgjsvmzvtadhimnvacljbhmzikeabhjoszfig...
output:
435002470
result:
ok 1 number(s): "435002470"
Test #21:
score: 0
Accepted
time: 382ms
memory: 151344kb
input:
aabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaab...
output:
571187577
result:
ok 1 number(s): "571187577"
Test #22:
score: 0
Accepted
time: 404ms
memory: 152104kb
input:
abacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaabacabacabaabacababacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaabacabacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaabacabacabaabacababacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaabacab...
output:
785945100
result:
ok 1 number(s): "785945100"
Test #23:
score: 0
Accepted
time: 436ms
memory: 153024kb
input:
abaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaa...
output:
501555951
result:
ok 1 number(s): "501555951"
Test #24:
score: 0
Accepted
time: 453ms
memory: 152688kb
input:
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...
output:
483421416
result:
ok 1 number(s): "483421416"
Test #25:
score: 0
Accepted
time: 439ms
memory: 152092kb
input:
abbcbcabbcbcabbcabbcbcabbcbcabbcabbcbcabbcabbcbcabbcbcabbcabbcbcabbcbcabbcabbcbcabbcabbcbcabbcbcabbcabbcbcabbcabbcbcabbcbcabbcabbcbcabbcbcabbcabbcbcabbcabbcbcabbcbcabbcabbcbcabbcbcabbcabbcbcabbcabbcbcabbcbcabbcabbcbcabbcabbcbcabbcbcabbcabbcbcabbcbcabbcabbcbcabbcabbcbcabbcbcabbcabbcbcabbcabbcbcabbcbc...
output:
610522803
result:
ok 1 number(s): "610522803"
Test #26:
score: 0
Accepted
time: 449ms
memory: 152524kb
input:
bacaacabacaabacabacaabacaacabacaabacabacaacabacaabacaacabacaabacabacaabacaacabacaabacabacaacabacaabacaacabacaabacabacaacabacaabacabacaabacaacabacaabacabacaacabacaabacaacabacaabacabacaabacaacabacaabacabacaacabacaabacabacaabacaacabacaabacabacaacabacaabacaacabacaabacabacaacabacaabacabacaabacaacabacaaba...
output:
688840647
result:
ok 1 number(s): "688840647"
Test #27:
score: 0
Accepted
time: 448ms
memory: 165124kb
input:
abbababbabaababbababbabaabbababbabaababbababbabaababbabaabbababbabaababbababbabaababbababbabaabbababbabaababbababbabaababbabaabbababbabaababbababbabaabbababbabaababbababbabaababbababbabaabbababbabaababbababbabaababbabaabbababbabaababbababbabaabbababbabaababbababbabaababbabaabbababbabaababbababbabaab...
output:
185974021
result:
ok 1 number(s): "185974021"
Test #28:
score: 0
Accepted
time: 437ms
memory: 152500kb
input:
abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabaiabacabadabacabaeabacabadabacabafabacabadabac...
output:
881963869
result:
ok 1 number(s): "881963869"
Test #29:
score: 0
Accepted
time: 455ms
memory: 164848kb
input:
aabbaaccaabbaaddaabbaaccaabbaaeeaabbaaccaabbaaddaabbaaccaabbaaffaabbaaccaabbaaddaabbaaccaabbaaeeaabbaaccaabbaaddaabbaaccaabbaaggaabbaaccaabbaaddaabbaaccaabbaaeeaabbaaccaabbaaddaabbaaccaabbaaffaabbaaccaabbaaddaabbaaccaabbaaeeaabbaaccaabbaaddaabbaaccaabbaahhaabbaaccaabbaaddaabbaaccaabbaaeeaabbaaccaabb...
output:
647864259
result:
ok 1 number(s): "647864259"
Test #30:
score: 0
Accepted
time: 383ms
memory: 151264kb
input:
ddrddrdddrddrdddrddrddrdddrddrdddrddrddrdddrddrdddrddrdddrddrddrdddrddrdddrddrddrdddrddrdddrddrdddrddrddrdddrddrdddrddrddrdddrddrdddrddrddrdddrddrdddrddrdddrddrddrdddrddrdddrddrddrdddrddrdddrddrdddrddrddrdddrddrdddrddrddrdddrddrdddrddrddrdddrddrdddrddrdddrddrddrdddrddrdddrddrddrdddrddrdddrddrdddrddr...
output:
611194463
result:
ok 1 number(s): "611194463"
Test #31:
score: 0
Accepted
time: 420ms
memory: 153168kb
input:
hehfhehhehfhehehfhehhehfhehfhehhehfhehehfhehhehfhehhehfhehehfhehhehfhehfhehhehfhehehfhehhehfhehehfhehhehfhehfhehhehfhehehfhehhehfhehhehfhehehfhehhehfhehfhehhehfhehehfhehhehfhehfhehhehfhehehfhehhehfhehhehfhehehfhehhehfhehfhehhehfhehehfhehhehfhehehfhehhehfhehfhehhehfhehehfhehhehfhehhehfhehehfhehhehfhe...
output:
350121745
result:
ok 1 number(s): "350121745"
Test #32:
score: 0
Accepted
time: 433ms
memory: 152148kb
input:
nmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnmnnmnnmnmnnmnn...
output:
533553735
result:
ok 1 number(s): "533553735"
Test #33:
score: 0
Accepted
time: 382ms
memory: 151744kb
input:
joojojjoojjojoojojjojoojjoojojjoojjojoojjoojojjojoojojjoojjojoojojjojoojjoojojjojoojojjoojjojoojjoojojjoojjojoojojjojoojjoojojjoojjojoojjoojojjojoojojjoojjojoojjoojojjoojjojoojojjojoojjoojojjojoojojjoojjojoojojjojoojjoojojjoojjojoojjoojojjojoojojjoojjojoojojjojoojjoojojjojoojojjoojjojoojjoojojjoojjo...
output:
177198028
result:
ok 1 number(s): "177198028"
Test #34:
score: 0
Accepted
time: 447ms
memory: 152416kb
input:
qddhdhqddhdhqddhqddhdhqddhdhqddhqddhdhqddhqddhdhqddhdhqddhqddhdhqddhdhqddhqddhdhqddhqddhdhqddhdhqddhqddhdhqddhqddhdhqddhdhqddhqddhdhqddhdhqddhqddhdhqddhqddhdhqddhdhqddhqddhdhqddhdhqddhqddhdhqddhqddhdhqddhdhqddhqddhdhqddhqddhdhqddhdhqddhqddhdhqddhdhqddhqddhdhqddhqddhdhqddhdhqddhqddhdhqddhqddhdhqddhdh...
output:
101237979
result:
ok 1 number(s): "101237979"
Test #35:
score: 0
Accepted
time: 419ms
memory: 152576kb
input:
dqvqqvqdqvqqdqvqdqvqqdqvqqvqdqvqqdqvqdqvqqvqdqvqqdqvqqvqdqvqqdqvqdqvqqdqvqqvqdqvqqdqvqdqvqqvqdqvqqdqvqqvqdqvqqdqvqdqvqqvqdqvqqdqvqdqvqqdqvqqvqdqvqqdqvqdqvqqvqdqvqqdqvqqvqdqvqqdqvqdqvqqdqvqqvqdqvqqdqvqdqvqqvqdqvqqdqvqdqvqqdqvqqvqdqvqqdqvqdqvqqvqdqvqqdqvqqvqdqvqqdqvqdqvqqvqdqvqqdqvqdqvqqdqvqqvqdqvqqdq...
output:
292588879
result:
ok 1 number(s): "292588879"
Test #36:
score: 0
Accepted
time: 408ms
memory: 152032kb
input:
axxaxaxxaxaaxaxxaxaxxaxaaxxaxaxxaxaaxaxxaxaxxaxaaxaxxaxaaxxaxaxxaxaaxaxxaxaxxaxaaxaxxaxaxxaxaaxxaxaxxaxaaxaxxaxaxxaxaaxaxxaxaaxxaxaxxaxaaxaxxaxaxxaxaaxxaxaxxaxaaxaxxaxaxxaxaaxaxxaxaxxaxaaxxaxaxxaxaaxaxxaxaxxaxaaxaxxaxaaxxaxaxxaxaaxaxxaxaxxaxaaxxaxaxxaxaaxaxxaxaxxaxaaxaxxaxaaxxaxaxxaxaaxaxxaxaxxaxaax...
output:
663737748
result:
ok 1 number(s): "663737748"
Test #37:
score: 0
Accepted
time: 399ms
memory: 152648kb
input:
pgpepgpwpgpepgpopgpepgpwpgpepgptpgpepgpwpgpepgpopgpepgpwpgpepgpdpgpepgpwpgpepgpopgpepgpwpgpepgptpgpepgpwpgpepgpopgpepgpwpgpepgphpgpepgpwpgpepgpopgpepgpwpgpepgptpgpepgpwpgpepgpopgpepgpwpgpepgpdpgpepgpwpgpepgpopgpepgpwpgpepgptpgpepgpwpgpepgpopgpepgpwpgpepgpypgpepgpwpgpepgpopgpepgpwpgpepgptpgpepgpwpgpe...
output:
488572018
result:
ok 1 number(s): "488572018"
Test #38:
score: 0
Accepted
time: 443ms
memory: 152552kb
input:
rrwwrraarrwwrrssrrwwrraarrwwrrjjrrwwrraarrwwrrssrrwwrraarrwwrriirrwwrraarrwwrrssrrwwrraarrwwrrjjrrwwrraarrwwrrssrrwwrraarrwwrrggrrwwrraarrwwrrssrrwwrraarrwwrrjjrrwwrraarrwwrrssrrwwrraarrwwrriirrwwrraarrwwrrssrrwwrraarrwwrrjjrrwwrraarrwwrrssrrwwrraarrwwrrddrrwwrraarrwwrrssrrwwrraarrwwrrjjrrwwrraarrww...
output:
686260254
result:
ok 1 number(s): "686260254"
Test #39:
score: 0
Accepted
time: 426ms
memory: 153568kb
input:
jmgfgawmrduominxypmrqdincccsmkfkkoqrzzmpnfnbtyxetgmfvyjugkvjvlfkjikyakiwuwjepviiwfgbenzycnqndaukmyknehgmlizltmebgvgmoebwijqvtwngbmojualcabcbafifsbmbtidqsjhxwyqautkjqztkhmusuixxanobxuaqlrmtmkprqpofxtkqviqqjgqcwrkbgdomrdtvjrjduuocsaxftjjulzpexmeigvmoxksccoepcjqdtcbbthjgdnsmnwklfrvlhazvcrbmkegnmmvdpcap...
output:
293683143
result:
ok 1 number(s): "293683143"
Test #40:
score: 0
Accepted
time: 429ms
memory: 162180kb
input:
dfddeeadfbgfcadcbbaaefgcchdhfcbagaedgdhafdhbffggfechccdhadbcchgeaeagfaaagfbeabffdaeefaaabbggffghbgfhbcahhdfdgccgegdgdhafhcdgbebcbbggegcachhefhcgfgcaececacagedaacfbcdgecghfedffchhaeabfbeehfeeddfecfefahbfaghbhbhdgddfgcdbfbeaahbcdhfdbeebhfbehggcfbabbfchggchhahehgfgbhaeebafbdacccffdfgfbhecebgfeeebdacaaa...
output:
896912463
result:
ok 1 number(s): "896912463"
Test #41:
score: 0
Accepted
time: 435ms
memory: 158512kb
input:
djkdjdlkbamfcmacgaekgbgmimadajicdbgmiejaacggablfgejfgmafmhbcifaehamkadfcglbmhhblgalklhglicmhakfjaafidjmihmghgbhdhjfdllmaekkeklccadieaibeiddjefjleaiegkllmeglgedeleabgghdaidgehdacemkbaddalkamgiffgdcbhhckhmacimaeamehiigfggmglccidaffjcjijafmbehlgglcmacifjgmdfcdahfljdhfjkijcdebkkhgbdlijcabjbgefchjdbfigbi...
output:
866183470
result:
ok 1 number(s): "866183470"
Test #42:
score: 0
Accepted
time: 431ms
memory: 158652kb
input:
akejekgcbkkajhbmklibdmdfmllhgheagfjjbbifdjeglcmmbhmglebljhfmdidckdjebldeffdelakbfckhdmlmickdfedimjjmjdhlmikgabblgifdcbacgkchmfkhflgggakalkihlllakglmaeldhjljfhegalcmgkhleahciagicfljkkkdajbdkhelfmlmcgmdegkaekdmckbfhgjdmhgbkihahbgmgbiadkidijecgdambchefefjklfhdhjamhkeefedffjlckfhjdfkimelbfjliamccfkaljck...
output:
490416632
result:
ok 1 number(s): "490416632"
Test #43:
score: 0
Accepted
time: 466ms
memory: 163828kb
input:
dccfccebfcbbabcddeecfeaecfdbbbdfadcdafbfbbeeefgceegabdbbdeacbafdbdgaegadfddeaegcbcgcdggeefffecfaadabdbeaeebfbagdggfbbfeddgedcfgfafecedgffadeagggeababdfdbcbdeafabdggaccaaacedccegccaadebdebdfabaffcbdcbcfcdgabcabdcebfcbgecgdddcedaaeeefgfbgbdbbfeffadbecddffedddffadbeeaegaacegegcagefcffababbdaafdfgegfdbb...
output:
885724660
result:
ok 1 number(s): "885724660"
Test #44:
score: 0
Accepted
time: 455ms
memory: 157152kb
input:
aehhddeelhbahadgalifaklhccaefgcbhglheiaeahgffkblkafhcfdebggdkdhdjgkjaekhflfehlkdcbejagigdlcabkblijfecgdbikehhekhihehhebalgjfjcehkdajcakehbiedbcjdfhacdhcckhdjbfjdllaajdckhjaglbdaalbihbjlheklkiaabkfjbhchjlkealbdlgkdahihgigcfdjflfdhejbedgajbfbhlkhgcglkdhclcelgkldegkgfekajdljfiaagbkkdbfdafdkcfgjhlfjdidd...
output:
421010120
result:
ok 1 number(s): "421010120"
Test #45:
score: 0
Accepted
time: 432ms
memory: 156688kb
input:
ikiajgmoobiibgmncbfmmabkagcegdloelekkeaebjcemcklemhiiomiabiihmccignhfifmdccmgdljhdlglbamfaafgddehngkimkflcdijdclhjookhnkdjkooalhchiikgjcemmigkhbkoafnglokmdkmcmmdgdfngcgfcglbkifnhaflfgdmdchdbaofhnhiadfoocoljghnbdfcohgeimonabgbjiekfdogkbdlfaiomkclaklnbeolnfhamekgdkmbfmjfofkkkoknlifehgaeimbaaahfdhekkbb...
output:
249065158
result:
ok 1 number(s): "249065158"
Test #46:
score: 0
Accepted
time: 448ms
memory: 154924kb
input:
bbidjtskemfoqflkgitiksamhiskmkdbieeethgsisgruqdjrbepunqfrorcmgaomlrntjjcrgobhmkjsfjqbschsfamsjsgcqishmaanbkhaechktgejonmnoltjgsunjpjicuplglpsgeiqtfrpbrmrbajenmeceikhgndkigrbubjdnlmpikpnpcsprmefffpmmmrcbmhghpjaanksmldikhobiajjpgfbnjnqgibdelmhhtqeshlmhsbunjcahmnjgpfphhcrfkinleassgogqjlecefedhfsicioksi...
output:
696887551
result:
ok 1 number(s): "696887551"
Test #47:
score: 0
Accepted
time: 439ms
memory: 155160kb
input:
amdhpchjhekifhphbcmhhhdiomjnbogojfqaknelnpjqlioflclmobhpofqfafnnogjblabnnignbclfcmhgooaeiohadbeihmbpgollbkaiipaaoophogjmodiqmjagjoqlnbkagfgpfiedbijagqhmfbigekqppielgcdfkennghqelpmelfepfgelqehnogggaobqclnamimfcooikpcliiglolhjcnoekqqfkhbnjafdfipjdlphcpidlbchdapjblaebchmamlhgllbipgqhlbhpfcnnjodgjdfcqmp...
output:
243281615
result:
ok 1 number(s): "243281615"
Test #48:
score: 0
Accepted
time: 391ms
memory: 151700kb
input:
dbeafaheacadbefjhabeegbaicejbbdgjbeghjbhdhddachigjffakkdkeahciadejkfkfaccdgjkfkdkkgcbggibagikedhejecahhchhkcebbidihjbkjegaakikdfihfhebbccfikhacdedaiaffhfkecagbcbjgbbffafdacfeeibdjhjjddjhkdkihhdhgijdjfdcjagjfafdahfjgkkjachjcdicaieeafhdfjfhchahiidhhfkaghbegbgcfefkijhdebejjjidcadkchgigdeiecfjhfjkefiekk...
output:
678667698
result:
ok 1 number(s): "678667698"
Test #49:
score: 0
Accepted
time: 424ms
memory: 155852kb
input:
deoojpgcgpkoholhlcfddeohkqoihkcalfngpkcabbkimgpkccaqapjcciehchiqbjqjpkbenflbbmqlgogkkqlaoaenoahilflhjrkibcjpndignjkjdilkfjcgonlhfhqokdkqfcooddnqraffljggmefpjaqgdqbhgfkpcionmhnkieocrokobhgnpkkqamjdalqjnefhofndmgialqhmfjnkjnqhmcjnddbkmdnbfokfmbihnnobcakhjmnfmrfganfhicdlmlgqfdqrcnidldqpkpniojdkabeorrci...
output:
640377934
result:
ok 1 number(s): "640377934"
Test #50:
score: 0
Accepted
time: 413ms
memory: 153460kb
input:
rcplswkqluujkpofiplijbkfamjnpmwbetfaolnjlwjeklpmqnuduqdlbvohfebccbdgsmlumlsbmepaqcsdhsdiqmcgmrtmkneoqitmiiamfkcakoqivniqkarnptorecjpnhjrilbhqlqsiiqcaoequooccldcicgjgvesjkothbqrkmwqjmgpiviesqdsbvcvwbkewqkdjathbpodcwbcaapijiwmdalphlerftsvpctpgilajbthfclwhnpaqrmpulnkouchahefqhuodqudvvlkhuqjbfirnbomnblm...
output:
66403201
result:
ok 1 number(s): "66403201"
Test #51:
score: 0
Accepted
time: 442ms
memory: 153504kb
input:
kcelopohpkauakpqbkkffonjqopuccmehqsssbscqgkmbkmrhccdriukchfjhooedrpidupnhrruqjhlcolrtsjehqqtpknjqsgklfjpirsnqfjlhscetstgrlilmdicgaafhasapptemkeaonlohgrtnoqtaghbbmaskprseerhsdrsacrscpgkbrlqeesgdhabhklbapimgnbidlskjhacqbfgbbgjhbqqjmksatqqcrfpqplttotunndmlmcifiqkdfkbeoofkueargstanfpoqjcgipqbhqsisqqupua...
output:
674574764
result:
ok 1 number(s): "674574764"
Test #52:
score: 0
Accepted
time: 427ms
memory: 153672kb
input:
lokefigibdllifnkjkhnimgelligecajbonifkiahfaglcabobfnjiaffhkjebdcmflhimlfdofookcmmoaehhhjiiolglcdemjlmiimjelihecabcecbehmlefaackglgkelkihnlbgnhhodeeejnokhknomgibjjiglacgkanjmeiejagggbledmhgaaekimngheheihggogbjfldlbfoelngooilkenmkmlbliejdfhgalhbfihkicbnckjlfnfmcfcgojmcnnifkhfafmhohohkfchibbbmmbhhanhbc...
output:
102969525
result:
ok 1 number(s): "102969525"
Test #53:
score: 0
Accepted
time: 412ms
memory: 155612kb
input:
jhuuccdtstliggpntpafkqniscpsoprtdoekmrrdilfcgfjmjmmdtfblsabqnubkufsmscrbosqpsbidqfjtgaaaiafmkjqjkhqaqrtooaujonhdjebsfakbhqnitrgjlgaiknktoktjsdiktcotccnrpefcbnqnhmlapoiamukspsufbumacjikgpehhhbnkirtnmtamckhfhcuhbflosfhhlqipupjkhcdbgakqpcjrpfmlmtkrtibuhrndkrurjgpqlglsggtetiathbtnckdqgofakuiumsfqmchppao...
output:
305160976
result:
ok 1 number(s): "305160976"
Test #54:
score: 0
Accepted
time: 401ms
memory: 151552kb
input:
pghtgnactijlrpguqmmclmonmvptpqlcrnuktgdvephiiklfdrrtrhnejnqceimfjuinqeuhhqkauvktipashuvjthvcgdlqsorggmrlemsncuqbjmjkahmhmhhjbjsgbbhsrpttdkhfcbdjemovvbmeaifrneritlqvurjdjmjjvppitgckjmdtldoimosvrdlqqqvnsurlilhecbsdnvncsdqbvddodohpofabdpcekvokkgtbppoapfliiriaouldpbrsfhnagsjojejcuithqsjoelpqsjnaurulpsar...
output:
564861703
result:
ok 1 number(s): "564861703"
Test #55:
score: 0
Accepted
time: 428ms
memory: 153632kb
input:
oihhieeoadhlkggfalmodcmedfmdbfedcflnlbfjjcbgccifnmieinnbkcfjegkdmcaoenbjhgihdgodoamklmklhgcoiemjahgnmaamdkjnafmdegfdhaefggjbonegcmmkldjlhgdofhfbaloiljelongglooakkccbgholfbooobjfocekldinlokadkdonkibanjomeonialbhhokaniadhijldmnilcmebabohaeeicimjemlajcbkojoonenhlabobhfajenedjdoniejlkincbdjifbajkcakgmnl...
output:
487389185
result:
ok 1 number(s): "487389185"
Test #56:
score: 0
Accepted
time: 425ms
memory: 155472kb
input:
mbecsnmaqpqeehmgmfdoaobhqkpmgqariegclsokjnosbbbgdgggcelaamnjoqbqglbsqhafppihnocmalqanasodafckknjpajdabinmgicqionaffaajppfdfibanfjhdforpikceonnaciharfmmsnesknfchhnorkkminlmhkcsijaescaqjbckgicsffecdchbdieomkbsqalncjllhpiphmprsehrlqfjaedbbojqblaaprsoldfjqqckesbomjdgqokdmrpoffhjfbeckkcofmcphbmqeokflmjrq...
output:
429687603
result:
ok 1 number(s): "429687603"
Test #57:
score: 0
Accepted
time: 461ms
memory: 177716kb
input:
aabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaabaabaaabaabaaabaabaabaaabaabaaabaabaaabaab...
output:
394014419
result:
ok 1 number(s): "394014419"
Test #58:
score: 0
Accepted
time: 423ms
memory: 176384kb
input:
abacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaabacabacabaabacababacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaabacabacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaabacabacabaabacababacabaabacababacabaabacabacabaabacababacabaabacabaabacababacabaabacab...
output:
142112521
result:
ok 1 number(s): "142112521"
Test #59:
score: 0
Accepted
time: 446ms
memory: 177020kb
input:
abaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaababaababaabaababaababaabaababaabaa...
output:
610603128
result:
ok 1 number(s): "610603128"
Test #60:
score: -100
Wrong Answer
time: 469ms
memory: 177092kb
input:
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...
output:
636911765
result:
wrong answer 1st numbers differ - expected: '918562310', found: '636911765'