QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#854878 | #8668. 回文路径 | cyrxdzj | 100 ✓ | 537ms | 58764kb | C++14 | 8.2kb | 2025-01-12 10:30:51 | 2025-01-12 10:30:51 |
Judging History
answer
// Author: cyrxdzj
// Problem:
// A.
// 回文路径
// Contest: undefined -
// PKUSC 2024 Day 1
// URL: https://qoj.ac/contest/1659/problem/8668
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
using namespace std;
//#define debug
const int MAXN=3e5;
const int MODCNT=2;
const long long BASE[MODCNT]={29,31},MOD[MODCNT]={998244353,19260817};
int n;
char s[2][MAXN+5];
int ans;
struct Seg
{
int l,r;
int mid,offset;
int len()
{
if(l==0)
{
return 0;
}
return r-l+1;
}
};
bool operator<(Seg a,Seg b)
{
if(a.l==b.l)
{
return a.r<b.r;
}
return a.l<b.l;
}
vector<Seg>seg_by_l[MAXN+5],seg_by_r[MAXN+5];
int corner_pt;
long long qpow_cache[2][MAXN*2+5],inv_cache[2][MAXN*2+5];
long long qpow(long long a,long long b,int id)
{
long long res=1;
while(b)
{
if(b&1)
{
res=res*a%MOD[id];
}
a=a*a%MOD[id];
b>>=1;
}
return res;
}
struct Hash
{
int len;
long long data1[MODCNT],data2[MODCNT];
Hash()
{
len=0;
for(int i=0;i<MODCNT;i++)
{
data1[i]=data2[i]=0;
}
}
Hash(char c)
{
len=1;
for(int i=0;i<MODCNT;i++)
{
data1[i]=data2[i]=c-'a'+1;
}
}
bool check()
{
for(int i=0;i<MODCNT;i++)
{
if(data1[i]!=data2[i])
{
return false;
}
}
return true;
}
void prt()
{
printf("%d",len);
for(int i=0;i<MODCNT;i++)
{
printf(" %9lld",data1[i]);
}
for(int i=0;i<MODCNT;i++)
{
printf(" %9lld",data2[i]);
}
printf("\n");
}
}pfx[2][MAXN+5];
Hash operator +(Hash a,Hash b)
{
Hash res;
res.len=a.len+b.len;
for(int i=0;i<MODCNT;i++)
{
res.data1[i]=((a.data1[i]*qpow_cache[i][b.len]%MOD[i])+b.data1[i])%MOD[i];
res.data2[i]=(a.data2[i]+(b.data2[i]*qpow_cache[i][a.len]%MOD[i]))%MOD[i];
}
return res;
}
Hash operator -(Hash a,Hash b)
{
Hash res;
res.len=a.len-b.len;
for(int i=0;i<MODCNT;i++)
{
res.data1[i]=(a.data1[i]-(b.data1[i]*qpow_cache[i][a.len-b.len]%MOD[i])+2*MOD[i])%MOD[i];
res.data2[i]=(a.data2[i]-b.data2[i]+2*MOD[i])%MOD[i]*inv_cache[i][b.len]%MOD[i];
}
return res;
}
Hash get_hash(int l,int r)
{
if(l==1)
{
if(r<=corner_pt)
{
return pfx[0][r];
}
else
{
return pfx[0][corner_pt]+(pfx[1][r-1]-pfx[1][corner_pt-1]);
}
}
return get_hash(1,r)-get_hash(1,l-1);
}
Seg get_reverse(int i,int offset)
{
Seg res=(Seg){0,0,0,0};
int extra=0;
int left=1,right=min(i,n+1-(i+offset)+1);
while(left<=right)
{
int mid=(left+right)>>1;
Hash tmp=get_hash(i-mid+1,i+offset+mid-1);
if(tmp.check())
{
extra=mid;
left=mid+1;
}
else
{
right=mid-1;
}
}
if(extra)
{
res=(Seg){i-extra+1,i+offset+extra-1,i,offset};
#ifdef debug
printf("%d %d\n",res.l,res.r);
#endif
}
return res;
}
vector<Seg>seg_insert_lib;
void seg_insert(Seg a)
{
seg_insert_lib.push_back(a);
}
void seg_commit()
{
for(Seg a:seg_insert_lib)
{
seg_by_l[a.l].push_back(a);
seg_by_r[a.r].push_back(a);
}
seg_insert_lib.clear();
}
int main()
{
scanf("%d",&n);
for(int i=0;i<=1;i++)
{
qpow_cache[i][0]=1;
for(int j=1;j<=2*n;j++)
{
qpow_cache[i][j]=qpow_cache[i][j-1]*BASE[i]%MOD[i];
}
inv_cache[i][2*n]=qpow(qpow_cache[i][2*n],MOD[i]-2,i);
for(int j=2*n-1;j>=0;j--)
{
inv_cache[i][j]=inv_cache[i][j+1]*BASE[i]%MOD[i];
}
}
for(int i=0;i<=1;i++)
{
scanf("%s",s[i]+1);
for(int j=1;j<=n;j++)
{
pfx[i][j]=pfx[i][j-1]+Hash(s[i][j]);
}
}
#ifdef debug_
pfx[1][n].prt();
(pfx[1][n-1]-pfx[1][1]).prt();
(pfx[1][4]-pfx[1][0]).prt();
(pfx[1][n]-pfx[1][1]).prt();
printf("%d %d %d\n",(pfx[1][n-1]-pfx[1][1]).check(),pfx[1][n].check(),pfx[0][n].check());
get_hash(1,2).prt();
#endif
for(int i=1;i<=n;i++)
{
for(int offset=0;(offset<=1)&&(i+offset<=n);offset++)
{
corner_pt=n;
int extra=0;
int left=1,right=min(i,n-(i+offset)+1);
while(left<=right)
{
int mid=(left+right)>>1;
if(get_hash(i-mid+1,i+offset+mid-1).check())
{
extra=mid;
left=mid+1;
}
else
{
right=mid-1;
}
}
if(extra==0)
{
continue;
}
#ifdef debug
printf("i %d offset %d extra %d\n",i,offset,extra);
#endif
ans=max(ans,extra*2-(offset==0));
corner_pt=i+offset+extra-1;
extra=0;
left=1,right=min(i,n+1-(i+offset)+1);
while(left<=right)
{
int mid=(left+right)>>1;
if(get_hash(i-mid+1,i+offset+mid-1).check())
{
extra=mid;
left=mid+1;
}
else
{
right=mid-1;
}
}
if(extra==0)
{
continue;
}
#ifdef debug
printf("i %d offset %d extra %d\n",i,offset,extra);
#endif
ans=max(ans,extra*2-(offset==0));
}
}
for(int i=1;i<=n;i++)
{
for(int offset=0;(offset<=1)&&(i+offset<=n);offset++)
{
corner_pt=1;
int extra=0;
int left=1,right=min(i,n-(i+offset)+1);
while(left<=right)
{
int mid=(left+right)>>1;
if(get_hash(i-mid+1+1,i+offset+mid-1+1).check())
{
extra=mid;
left=mid+1;
}
else
{
right=mid-1;
}
}
if(extra==0)
{
continue;
}
#ifdef debug
printf("i %d offset %d extra %d\n",i,offset,extra);
#endif
ans=max(ans,extra*2-(offset==0));
corner_pt=i-extra+1;
extra=0;
left=1,right=min(i+1,n-(i+offset)+1);
while(left<=right)
{
int mid=(left+right)>>1;
if(get_hash(i-mid+1+1,i+offset+mid-1+1).check())
{
extra=mid;
left=mid+1;
}
else
{
right=mid-1;
}
}
if(extra==0)
{
continue;
}
#ifdef debug
printf("i %d offset %d extra %d\n",i,offset,extra);
#endif
ans=max(ans,extra*2-(offset==0));
}
}
for(int i=1;i<=n;i++)
{
if(s[0][i]!=s[1][i])
{
continue;
}
corner_pt=i;
int extra=0;
int left=1,right=min(i,n-i+1);
while(left<=right)
{
int mid=(left+right)>>1;
if(get_hash(i-mid+1,i+mid).check())
{
extra=mid;
left=mid+1;
}
else
{
right=mid-1;
}
}
ans=max(ans,extra*2);
}
printf("%d\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 30
Accepted
Test #1:
score: 30
Accepted
time: 3ms
memory: 50324kb
input:
1000 mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...
output:
6
result:
ok single line: '6'
Test #2:
score: 30
Accepted
time: 6ms
memory: 49856kb
input:
1000 wvitzoxwlmhexjuqvoxksetoupgkhattucdzfevqorkdlsymjuvhobdrjsodtipwpfhipsdnyvqtsbbasrrvyybijzmpwseckztnpnkqswgkaeivflhwevhxcchjsnelqcixexkntwiuolsditpdwypgerzijziyrgqkwuucnqaehuwkpyrmwewjitvsaebyytznbtnkulnepceeloyjpfhcdpqfqhvzsmkcynjwztmkbnqaxnikfuiutocahdfbvsgdskgwqmzizzjlbqxnngftdohetabpjzpqzyc...
output:
7
result:
ok single line: '7'
Test #3:
score: 30
Accepted
time: 3ms
memory: 49996kb
input:
1000 abababaabaababbbbabbbbabbbbbbabbbaabbbaababaabaabbabbbbaabbaabaaaabbaaabbbbaaaaaabbbbababaababbaabbbbbbbbabbaababbbbabbaabbbabaaababbaababbbaabaabaababaaababbaaaababbbbbaaabbaabbaaabbaaaaabaaaaaabbbbbaaabbbbbaabbbbababaabaabbbbaaaaababaaaababbbbbbaababbbaaaababaabaabaabaaaaaabbabbabbbbbbbbbbabb...
output:
28
result:
ok single line: '28'
Test #4:
score: 30
Accepted
time: 10ms
memory: 49812kb
input:
1000 ababbababababbaababaaabaabaababbaabbbabaababbaaababbabbbbaabbababbbababbabababbaabbbaababbabaaaaabbbbbaaaaaaaaabbbbaabbbaabbababaaabababbaaaabababbbaabaabbabbaabaaaaaaabaaabaaababaaaababbaaabaabbbbbbaabbabaaabaabbbbabbababbbaaaaabbabbaabbaabbaabaaabaaabbbbbaabaaaaaababbbbbabbbabbbabababbbbbabaa...
output:
27
result:
ok single line: '27'
Test #5:
score: 30
Accepted
time: 4ms
memory: 49864kb
input:
1000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabba...
output:
987
result:
ok single line: '987'
Test #6:
score: 30
Accepted
time: 6ms
memory: 49820kb
input:
1000 aaaaaaababbabbabaabaaaaababaaaaaabaabaaaabaaaaaaabbbabaabbaaabaaaaaaabaaaaaaaabaaabbaababaaaaaaaaabbaabbabbaaaaabaaaaaaaabbaaabaaaaaaaaaaabaabbbbbaaaabaaaaaaaaabbbaaaaabaaabaaaaaaaaaaaaaababaaaaabbaabbaaaabaabaaaababaaaaaababaaaaabaaaaaaabaaaababaaaabbaaaabaaaaabaaaaaaaabaaaaaaabaaaaaaaaaaaabaa...
output:
45
result:
ok single line: '45'
Test #7:
score: 30
Accepted
time: 8ms
memory: 49948kb
input:
1000 aaaaaabaaaaaaaababaaaaaaababaaaabaabaaaaabaabaaaabbaaaaabaababaaaaaaaaaaabaaaabaaaaaaaaaaaaaaaaaabbaaaaaaababaabaaaabababaaaaabbaaaaaabbababaaabbaaababbaaaabbababaaaaaaaaabbbaaaababaaaaabaaaabbaabaaaaaabbaabaaaaaaaaaaabaaaababbaaaaaaaababbabaaaaaaaaabaaaabaaaaabaaaaaaaaaaaabaaaabaaababaabaabaab...
output:
45
result:
ok single line: '45'
Test #8:
score: 30
Accepted
time: 3ms
memory: 50460kb
input:
1000 aabaaaabaaaabaaabaabbbaabaabbbaaaaaaaaaabaaaaabaababaabaabaaaaaaaaaabbabbaaaaaaaabaabbbbbaaaabbabbbaaaaaabababbaaaabaaaaaaaaabaaaaaaaabaaaaaabbaaaaabaaaaaababaaababaaaabaaaaaabaaaaaaabaaaaabbaaaaabaababaaaabbaaabbaabaabaaaaababbababaaabbbabaabaaabaaabaababbabaababaaaaabaaababaaaaaaaaaabbaaaabaa...
output:
36
result:
ok single line: '36'
Test #9:
score: 30
Accepted
time: 3ms
memory: 49816kb
input:
1000 aaaaaabaabaaaaaaabaaaaaabaabaaaaaaaaabaabaaaaaaababaaaaabaaabaabaaabaaaaaaaaaaaaabbbbbabaaaaaaabaaaaabaaabaaaaabababaaabaaabaabaabaaaabbaabaaaaaaaaaaaaaaabbaaaaabaabbabbbaaabbbabaababbaabaaaabbaaaabaabbbaaaaaaaaaabaabaaaabbaaaabbbbaaabaaaaabaaababaaaaaaaaaabbabbabaaaaaaaaaaaaaaaabaababbaaaababa...
output:
50
result:
ok single line: '50'
Test #10:
score: 30
Accepted
time: 7ms
memory: 50288kb
input:
1000 aaccbdbabdaaddabaabaaaacbbccdbabbaacabcdababdcacadababaadaaaadabacababcdbaabaaaabdbabbdcaacccaaacababaacbcacaaabbabbaaabcbaaabaababbaaacbaacaaacabdccbbbaabaccacadbbcaabacadaababbaaabababbacaabbaaabcdaabaaaaaabaababaabcabacaabacaaaaaacaaabcbcabcbbcbbbaacaadadbadbbadcabababcabbcbbdadbdababaaadcab...
output:
20
result:
ok single line: '20'
Subtask #2:
score: 20
Accepted
Test #11:
score: 20
Accepted
time: 425ms
memory: 51272kb
input:
100000 ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...
output:
9
result:
ok single line: '9'
Test #12:
score: 20
Accepted
time: 409ms
memory: 56156kb
input:
100000 fruiifpdggdnsbgamakpjipicaidfdjpffioqcwioaafbpdagmbbakqpekjabcljockpvcifilcjakhcboolgjbnmmrbeawcjopbccjgncdaucighprheiaqofriccfdbydbhijeelbthsmqbhcddlfemqkvdbflkdrifckarqwlaafifmqibssfukblchalkzdefnccaiabrhcrmisdeiqddccrqhiiwcqqakbfhebkiecahgdlibhgmegkfbuibcarcbajpdeboigeoctdljmqeckdfqahiecla...
output:
9
result:
ok single line: '9'
Test #13:
score: 20
Accepted
time: 406ms
memory: 56624kb
input:
99999 biwnbsgdlxognjnepijlgbfbbahicjfqhdhcielcovdflacbrgcfapifaylqfmvipcccoofthuutfheboncacenchdgfljpidjbasdsikduidkbdqckmlnbfaidlincqkccbbpmnqnpbjoclgeduitraqmdfgdqinhddgberlbnlgggoafgqllbifekoccpgemcgdiiackkcfjgddhieabhzdjfwegcbuncdadebglitgwcbpmclfijmqtbbnbbrcehhanjgbddiaoimmkehtloreemecckjejifck...
output:
11
result:
ok single line: '11'
Test #14:
score: 20
Accepted
time: 406ms
memory: 56268kb
input:
99999 chgjcjipccsmclcpjqmbrcpaqdggbdodxbcejbklpjhkefeidkjojjjbljhtykbcdgnnjeictgjgliegyfilmlkqkgddpefibjusamblbpqfbbvcfkgfagikbujlbjvenjbmcadceadnltdeksatckmkjkscojeqbpaaglggxhideqhkhibchdasadfggcoihhcwlphbeevohhohtthepedqfggbdglidnatocrkhnkijraddqbesaiajimdhdmvbgodlcglqqmkeehcfabeaatjdinzhijewfoxhh...
output:
9
result:
ok single line: '9'
Test #15:
score: 20
Accepted
time: 395ms
memory: 56444kb
input:
99999 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok single line: '99999'
Subtask #3:
score: 50
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #16:
score: 50
Accepted
time: 399ms
memory: 56296kb
input:
100000 vucutyzmjlnyadjbpqkrlqvzuponzxrvqsqqgbemhzjftdkksfgspeuonmjwlbirvszhcafcxpeubixvxetwyyqmftbobhodwaiwrcwdvddohalyqgaatvpflorvjypszbvzpwiaxxgievaozquixcndkxqfxcxaiygyqcgdebogwzquvqfljgjcvvhpirfzqlkwctibngdsffpormliyhrkcbxwxoaoovaawldfenziwnlahllzhjsvdhzekcqekayusmvzrgsdiiymjxfiddhawhgxathvnsedf...
output:
10
result:
ok single line: '10'
Test #17:
score: 50
Accepted
time: 399ms
memory: 58764kb
input:
100000 fotxrzsqxuaaiiqmiymhtfdipylgdmxizgzqrgbrmdemonbisusgbmmsgtyoaqgdmxwoxayxkszpvpypzjoapilopvhyiyhckcccaalqriunudgfifgvdiufjtukpsmdfjjzftszwizrwoxuqsujchtrywpiiineoscbvarbalizfyydbctxpuwndzgshavpygfcmxkorbcppbatauqqkumaqsjcupnihewaukjajqgdvatobxjgdcbevlxpkjdvpofwtctivkexpwnbwvwbhcmlivuvifpptiupy...
output:
9
result:
ok single line: '9'
Test #18:
score: 50
Accepted
time: 499ms
memory: 56296kb
input:
100000 baaabababbbaabbbbaabbabbababbbbbaaaaabaabbbbbbaaabaabaaabababbabbabbaababbaababbbabaaaaabbbabbabaaaabaabbbbababaaaaabbbbbabbbababbbbbaaabbaaabaabaaababbababbabaaaaaaaababaaabaababbbababbbbabbbabaaababbababbbababaabbaabbabaaaabaaabbbabbaabbabbbbbbabbbbaaaaaaaaaaabbbaabaaaabbbabbbaabababbbbaabb...
output:
40
result:
ok single line: '40'
Test #19:
score: 50
Accepted
time: 505ms
memory: 56268kb
input:
100000 babbbbaabaaaaaaaaaabbbbababababababababbabaaabbaaaaabaaaabaaaaababaabaabaabbbbabbbaabababbbaaabaaaaaaababaabababababbaabbbaabaabbbbbbbabaabbaabaaaababbbaabaaabaaaabbabbababbaabbabbbaabbbaababbaabaabaabbabbbabaaaaaaaaaabaabbabaaaaababaabbababbbabababbbbabbbbababababaabbabbababbaababababbbbaaba...
output:
43
result:
ok single line: '43'
Test #20:
score: 50
Accepted
time: 537ms
memory: 58388kb
input:
100000 aabaabbaaaaabbbbbaaaaaaaaaaaaaabbaaaaaaaaabaaaabbaaaaaabaaaaabaabbaaabababaaabbaaaaaaaaaabbabbbaaaaaaabaaabbbaabaaabaaabaaaaaaaaaabaabaaaababaaaaaabbaaaaaaababaabaaaaabababaaaaaaaaaababaaaababbaaabaaaabaaaaabaababbaaaaabbaaabaabaabaaaaababaaaaabbaaaabaaaaaaabaaaaaaaaabaabaaaaaabaababbbabaaaba...
output:
75
result:
ok single line: '75'
Test #21:
score: 50
Accepted
time: 533ms
memory: 58388kb
input:
100000 aaaabaabaaabaabbaaaabbbaaaaaaabaabaabaabaaaababaaaaabaaaaabbabaabbaabaaaaaabaaaaaaaaaaaaabaabbabaaaaaabaaaaaaaaaaaabaaaabbbabaaaaaabaaaababaaaabaaaaaabbaaaaaaaaabababaaaaabaabababaaabbababaaaaababababbaaaaaabaabaaaabbababbbaaabaaaabaabaaaaabaabaaaaaabbbaaaaaaabababababbaaabaaabaaababaaaabaaaa...
output:
58
result:
ok single line: '58'
Test #22:
score: 50
Accepted
time: 517ms
memory: 56340kb
input:
100000 abbaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaabbabaaabaaaaaaaaaaaaaaabaaabbbaabaaaaabaaaaaaabaaaaabaabaabaaaababaaaaaaaaaaaaaaaaabaaabbabaaaaaaabaaaaaaabaaaaaabaaaaabaaabbaaaabbaabbaaababaababaaaaaabaaaaabaaaaaaaaaaaaababaaaaabaaaaaabbbabaaaaaaaaaaaaabaaaaaaaabbbaabaaabaaabaaabbabaabaaabbabaaaaaaaabba...
output:
67
result:
ok single line: '67'
Test #23:
score: 50
Accepted
time: 535ms
memory: 56208kb
input:
100000 bbaaaaabaaaaaaaaaabbaabaaaaaaabbbaabababaaababbaaaabaaaaaaaaaabaaaabbaaaaabaaaaaabbaabbbbaaabbaaaaaabbabaaabaababbaababaaabaaaaaaaaaabaaaaabbaaaaabbaaaabaaabababbbaabaaaaabaabaaaaaaabaaaaaaabaabababbbaaaaaaaaaaaaaaaaabaaaaaaabaaaaaababbbababaabaaabbbaaaaabaaaaaaabaabababaaaaaabaaaabbaabababaa...
output:
55
result:
ok single line: '55'
Test #24:
score: 50
Accepted
time: 462ms
memory: 56268kb
input:
100000 cabcacbbacbbaacbaabbaabbaabacdcadbbccabbccbbaabacacbabaccbaabbbaaabaddbcaccdcaababaaabbbbbcdacaabababcbbcbcabbbdbbbcadaadabcabbacabbdbbcaaabacaabbabbabacbabbabaadabbabdbabcbdcaacaddbbbabdabaaabcabcababbcbbaaccabbbbacaabbacdaaaabaaaaccaaabaaccbaccbbababdacaacabcaaabbaaacbcbaaabcaaabcaabbabbcad...
output:
25
result:
ok single line: '25'
Test #25:
score: 50
Accepted
time: 459ms
memory: 56296kb
input:
100000 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbab...
output:
96421
result:
ok single line: '96421'
Test #26:
score: 50
Accepted
time: 0ms
memory: 47996kb
input:
5 pkusc pkukp
output:
6
result:
ok single line: '6'