QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#563033 | #3844. LCS Spanning Tree | AmiyaCast | AC ✓ | 1243ms | 167848kb | C++14 | 3.1kb | 2024-09-14 00:37:04 | 2024-09-14 00:37:05 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pii make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,b,a) for(int i=b;i>=a;--i)
const ll inf = 1145141919810;
using namespace std;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
inline void print(ll x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
return ;
}
inline void pprint(ll x){print(x); puts("");}
//使用说明:
//sa rk下表都从0开始
//h代表的是排名这个和他后面的那个的lcp
//使用方法:转化成int数组
struct SA {
int n;
vector<int> sa, rk;
vector<ll> h;
SA(int *s, int _n) {
n = _n;
s[++n] = 200000000;
sa.resize(n);
h.resize(n - 1);
rk.resize(n);
iota(sa.begin(), sa.end(), 0);
sort(sa.begin(), sa.end(), [&](int a, int b) {
return s[a] < s[b];
});
rk[sa[0]] = 0;
for (int i = 1; i < n; ++i) {
rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
}
int k = 1;
vector<int> tmp, cnt(n);
tmp.reserve(n);
while (rk[sa[n - 1]] < n - 1) {
tmp.clear();
for (int i = 0; i < k; ++i) {
tmp.push_back(n - k + i);
}
for (auto i : sa) {
if (i >= k) {
tmp.push_back(i - k);
}
}
fill(cnt.begin(), cnt.end(), 0);
for (int i = 0; i < n; ++i) {
++cnt[rk[i]];
}
for (int i = 1; i < n; ++i) {
cnt[i] += cnt[i - 1];
}
for (int i = n - 1; i >= 0; --i) {
sa[--cnt[rk[tmp[i]]]] = tmp[i];
}
swap(rk, tmp);
rk[sa[0]] = 0;
for (int i = 1; i < n; ++i) {
rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] || sa[i - 1] + k == n || tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
}
k *= 2;
}
for (int i = 0, j = 0; i < n; ++i) {
if (rk[i] == 0) {
j = 0;
continue;
}
for (j -= j > 0; i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1] + j];)
++j;
h[rk[i] - 1] = j;
}
}
};
const int N = 4e6 + 7;
int fa[N];
int get(int x){
return fa[x] == x ? x : fa[x] = get(fa[x]);
}
int pos[N << 1], cnt[N];
struct Node{
int x, y;
ll lcp;
bool operator < (const Node o){
return lcp > o.lcp;
}
};
int s[N];
int main(){
int n = read();
srand(time(0));
cnt[0] = 0;
int m = 0, pt = 30;
rep(i, 1, n){
fa[i] = i;
string t;
cin >> t;
s[m++] = ++pt;
for(auto c:t){
s[m++] = c - 'a' + 1;
}
cnt[i] = m;//cnt是每个分隔符的位置
rep(j, cnt[i - 1] + 1, cnt[i] - 1) pos[j] = i;//表示时第几个串串
}
SA sa(s, m);//m代表长度
vector<Node> ans;
for(int i = 1; i < m; ++i){
if(pos[sa.sa[i]] == 0 || pos[sa.sa[i - 1]] == 0) continue;
ans.pb(Node{pos[sa.sa[i]], pos[sa.sa[i - 1]], sa.h[i - 1]});
}
sort(ans.begin(), ans.end());
ll Ans = 0;
for(auto x:ans){
int fx = get(x.x), fy = get(x.y);
if(fx == fy) continue;
Ans += x.lcp;
fa[fx] = fy;
}
pprint(Ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9780kb
input:
4 icpc macau regional contest
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 10004kb
input:
3 ababa babab aba
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 432ms
memory: 98528kb
input:
26 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 9916kb
input:
7 jia ran jin tian chi shen me
output:
9
result:
ok single line: '9'
Test #5:
score: 0
Accepted
time: 1ms
memory: 9848kb
input:
10 theysaynothinglastsforever weareonlyheretoday loveisnowornever bringmefaraway takemetoyourheart takemetoyoursoul givemeyourhandandholdme showmewhatloveis bemyguidingstar itiseasytakemetoyourheart
output:
55
result:
ok single line: '55'
Test #6:
score: 0
Accepted
time: 0ms
memory: 10220kb
input:
100 dblkekaekijliimalcaidjjfaghdmhifkiebieffbddjmflkhagajcfmkccjjadgiijdbdldgbbhgcfdcadbeiabkemiefdccmhdcfilhkfabmfdmigfgigdcibgaeicedfiidgecbhdamiaiefbmbgbjhklbhafmhckklbmmiemkcbfgjihmdjkai bciiecmbc cdjailkkbefkbmlekiefdhklcbdccfbgkagflfemjjmkjmcgiibldlmhbcldjajgafmakfbhecgcckkkglklljhmliehidbkicm...
output:
476
result:
ok single line: '476'
Test #7:
score: 0
Accepted
time: 316ms
memory: 100516kb
input:
2000 ecbhcebgbcjgjiihdefajfbbaajfjdedggciaegdiijhijgedbgejhgjjfhabdfhbihdeegcehbcjhgebcjachbdeiefejefhcjdihfcfgeegdahhjhjiiffjjadifiijjbhhjjeffabiaagcjhaachjbiecfeceefddecjchjfibgedfdghgdijdcdahfeddjihbhbbghjjffdcibaggiiadbaajhfcgdbaafbicahjhabfdbeacccfdehebciafaaffdfjdciafbhidbahdccjhjdadcciecfbhac...
output:
17765
result:
ok single line: '17765'
Test #8:
score: 0
Accepted
time: 321ms
memory: 97032kb
input:
1413 gjjmlceglbmbibjmmfcfmickcllfekgmicmifdbfgdgbeecgjgalbfkdfljjkclfgkaacdgigblaiaiehkeiccbjamikdgcjfemhhfebicddelklibjafmjhleebkimeblljfembgcgacdlkhjmbijjgacjaajebjfkcllffalheefeaedbmmkicaeecckdmedddbikeieimjmmcfdcgamicfbeimkjfamidjfhejdgiehkjkbdaaaeieldfibkkcgallieiamfehcdggiigkabblgigjgdlmflmafj...
output:
11429
result:
ok single line: '11429'
Test #9:
score: 0
Accepted
time: 468ms
memory: 167848kb
input:
2000000 j o v p h b t s x y u c t n p l b e c v d c p s u m d d i m h t a e j i i c c h d x j w m a j p f l n i q c c k q g q b u z u v d d f n i j v n i e l w h v m m i z w y d z l w h b x b a r y d x f r h p o u x u f u b c i p l j o j o n u k w x h z x z y d y d w h u k b u e i o g n y x y h l j ...
output:
1999974
result:
ok single line: '1999974'
Test #10:
score: 0
Accepted
time: 386ms
memory: 100720kb
input:
2 adwkgmoosmodblpylbpymmnbzyjzddfegdqppefjstpueeurhjpuvdxudgtgmaksfdjwhogcivwmbqeiavcxybubknkwqwqxzaujoclyzhnaztibonzpotsaicwaznyapujfwugvdtxfmhgcuhrlcklnminnxnoojzvfwbczubgijnldwcqzocodmdqltgzcguicwmdsombxbmcxotyfvmijsaulhtnppxtnkygakhzltbjjwjqrwyaozwzgroxhmquyocazjzkecvqzfgqdhttgpuojilqwbmurruscvd...
output:
8
result:
ok single line: '8'
Test #11:
score: 0
Accepted
time: 329ms
memory: 98948kb
input:
1413 ababaaaababbababbabbaababaabaaaabaabbabababbbabbaaababbbbabbababaaababbbaabbaaabaaabababbbbbbbabbaababbababaaabaabbaaaaabbbaaabbabaaabaabaababaaabbabbabaabaabbaabbbbbbabbabaaaabbababaabbababbbaaabababaabaababaaaabaaaaababbbbbbbbabbabaabbaabbbbabbbbbaaabbbbbaabbbaabababababaaabbaaaaabbaaaabaaaaa...
output:
42405
result:
ok single line: '42405'
Test #12:
score: 0
Accepted
time: 465ms
memory: 99676kb
input:
1413 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1995156
result:
ok single line: '1995156'
Test #13:
score: 0
Accepted
time: 340ms
memory: 100272kb
input:
1 baababbbbbaaabbaabbabaabbabaababaabaaabbbbbbbabbbababbbabaaababbbabbabaaabbbbbaabbaabbaabaaabaaaabbbabbbaaabbbbbabbbaaabaabbabbbbaabbbabbbababaaabaababaabbbababbabbbbaaabbaabbbbbbabbabaaaabaaaabbbaaabbbbbbaaabaaabbabbababbabaabbabababababbbbaaababaaaabaabaaababbbbbabbbaaaaaababbbbbababaabbbabaaaab...
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 620ms
memory: 98012kb
input:
1413 fnjfbnhskrerdxmxrlthhclkgcfrwukmccsfpbazsetxbfwvsseauqmcuutqofeshwxyxxasbtpfaocsgguayjcsdxitcnllliljglbjesqggubmbvozessjpcctrngdwsoedrpkjgsqatedrtfvlzhddjyvxfavxozcfooowhgzalctgjrriywmhvjeajzzxadepsslbbkdmpxsaoljmixvdgafpbgocjstdmegnrkbijvizjtnrqiwykdpmjfquxjympeziqdsbydahwpapyypkbfwmkohkxfwplv...
output:
464827
result:
ok single line: '464827'
Test #15:
score: 0
Accepted
time: 709ms
memory: 97756kb
input:
1413 vrotfwuoloxhchhuitgryunhjurviyookrumnoabeziigrdpmlglfvurrlmblapvtlkhbmkgmuosltjxerkkmfdfspgeqwbjhlslycrkwhehdohhhrtuwwbpmivegwppikaimtulbyugobnwvjsrhtivddzjcrbmbbupvoayoxefatdvexnmqxhwdjhfairbmlsjbvjrspwsibonydbrcinfrwkrfduropcrkljeahyijoxhryaujnzakmurpqkgfmxpxivzsuhbihkchnwsaxtmlpfbfphldgccrab...
output:
254582
result:
ok single line: '254582'
Test #16:
score: 0
Accepted
time: 574ms
memory: 99420kb
input:
1413 bbbbbabaabbabbbbbbaaabbaabaaabaabbabbaabaaabbbaaaaaabbaaabaaaabbabbbbbbbabbbbbabaaabaababbbaaabababbaaaaabbbbbabaaaabaaabbabbabbabaabaabaaabbbabbabaaababbbbbbaaaaababbabbbaabaaabaabbabbaaabaababaaabbbbabbabbabaaabbbabbbabbbbabaabbbabbbbabbbbaaabbbabaaabbaaaaabbababbababbbbbbaaaabaaaabaaaaabbabb...
output:
1498740
result:
ok single line: '1498740'
Test #17:
score: 0
Accepted
time: 536ms
memory: 100140kb
input:
1413 lcoqmejczgztniltuwtqgzmgyjdvkiqvlgozlzdmhchwksqerjuxkigjslgetycefqfqriezkmvwgndxyzvjiducocihbkogctyuecvqqqnxgsuerrpbwldkooupyixbdvxjzsaskppqhlvafmcbyfmmtgduqaxvxwfwohoawftfrofwahxyplmktpglrfjobolpxbsvhlaabhydrxeijqueibqzgzoipbzmctjlelnfsllllptufqaptqpzrdjgeluigdwlolsjzdwkusgcigrbzgcqlozpbvahzys...
output:
1285703
result:
ok single line: '1285703'
Test #18:
score: 0
Accepted
time: 646ms
memory: 98820kb
input:
500 eqrouzrzqavpwipjhbpbbsypakjkmpithzhdazdqzyivgzhpawsdorsrdcdstllansenrjgsjqqspxhrvaumtnfwrioktzmiusynbegluwdlvmcsoyghlleetuopwdzqxxdzdlmzjrkgdozunhbythfoetdaydswcxxgllfucsbhgcbtjduemztquysvdkrikqovbvpdnsmuwopitjmhkhyfiqaldtvnjjikhzpwubsqriymtnueuulcmnqrglepxobgqqcktvaldbzwovcirnneafvisczpsavisauo...
output:
93437
result:
ok single line: '93437'
Test #19:
score: 0
Accepted
time: 538ms
memory: 98876kb
input:
500 aababbabbbabbbaabbaaababaabbabbaaaabbaaababababbbbbbbaabaaaabaabaabaababaabbaaabaaabaaaaabaababbaabaaabaaabababbabaabaaabaaaabaaabaabbabbbbababbbbbbabbbbbabaababbabaaaaaaabaabababbaabbbbbbbaaaaababaababaabbaaabaabbbaaaabbabbabbbbaabbbbaaaaabaabbabbababbaaababaaabbbabbabaaaabbaabbababbbbabbabbbaa...
output:
621482
result:
ok single line: '621482'
Test #20:
score: 0
Accepted
time: 743ms
memory: 98428kb
input:
500 xkhhkzemvoilwwysloxrngtnalowphqotywezcsuqahpwhjjwjalpvysipqxyhoshkyioqchqlyothxrqacivacersdqbrkkdisuywdqibgdidwbfylbanhsfmkjgutlemfeiiusjaxuftvltgoutxoajajpwfbatiedtawcavwhptsizieufsxpuigqnjqguwknwirydqgujadlljfqeehynopazfhtetgabazgqhbzjgkupsltwusjijmkqtduomvpmwvcfydoeoluiypesjqbscnjxqdleacsyzwd...
output:
1305055
result:
ok single line: '1305055'
Test #21:
score: 0
Accepted
time: 728ms
memory: 99656kb
input:
500 afdppltdvwipholvfwehnlbcmcxujuxlbabqnwtiudzbunzzjfiwqjzclyzwswiuylmmjiwdlygflfhumrtcbuhosgnmexieivsrdpuopcwckdywwrzxliofqdswacaixtbckxtzzpbjubgqthqgrgmhjgdjidtiyukitdhuukeqmmhhvzpmfbvqjazsfuceqomjuwdoijhwvodqptewwzmgznafhejxsvimtldcvkasagjpbnnzpbhoohtxnewgceuvrxzojahjgsajhniwoqlezgbnlzvndpixpkly...
output:
1248710
result:
ok single line: '1248710'
Test #22:
score: 0
Accepted
time: 550ms
memory: 96988kb
input:
4000 gdlglqbydbkucqucvkhjoicbrutfyulgywmlpqlurxpvqhkywpnnwerqgjnnxyheruhcotfjpohhyrfwiulgbcyjnnwlofrfcykqspchfjqfcyemupuvutghifuykmeokohcfjlmueuycykwpeujzctkhpibmfvorjdmqztnqyqzjgzcsekanoxzescqxxeojjczivoywhzhpzjhftkvjhunzwfzwlphvsifpweldfstgdcoymjktfzvdfubqlilfqrvpxiuednlgqzhekrypstuxpwqagbgzubotli...
output:
587656
result:
ok single line: '587656'
Test #23:
score: 0
Accepted
time: 473ms
memory: 98140kb
input:
4000 baabaabbababbbbbabaabaabababaabaabbbabbaaaabbbabbaaababbbaaaabaababbbbbbbbaaaaabbabaabbabbabaabbaaabbbaaaabbbbaabaabbbbaabbaaaaaaaaaaaaabbbaaaabaabbbabbaabaabaaaaaabbaaaaabaaaaabbbaaaaabaabaaaaaaabbaabbaaabbaabaabbabbbaaaaaaabbbabbbabbaaabaababbaaabbaabbababaabbbbaaaaabbaabbbaaabbabababbbbbaaaa...
output:
867646
result:
ok single line: '867646'
Test #24:
score: 0
Accepted
time: 457ms
memory: 99648kb
input:
4000 baaaabbabbaaaabbbaaabbababaaaababbbaaabbbbbbbaabaabbbbbbbbbbbabbaabaabbbaabaabbaaaababbbaaabbbabaababaababbaaaaabaabbbabbababbbbbaaaaaaabbabababbaabbaaaabbbbababbbbbbaaaababbbbbbaababbaabbaabbbababbaabbabbaaababababaaababbbaaabbaababbbbbaaaabababaabbabaabaaaaabbaaaabbababaaaaaaababaabbbbabbbabb...
output:
870160
result:
ok single line: '870160'
Test #25:
score: 0
Accepted
time: 520ms
memory: 99720kb
input:
4000 jnbnjwgrxbxyqkbxyktdciatkisupcgkaanotwsywpwnczkakgfmohiypavecbrddgrwemuadsphrchdioswvaxnastcvmhasbwynsbsmqafsjjcybzvbwidqchnqpnjqjjfdkzpbzuvldyjgzejxpmntuajlpufrlzkaisoonwikhonlrvvrqszrenfgtmyeokhwcxkrwtbdjqqalltddvvhicqbroifyrbcootmjwrsmhuxspdykahscxwtnganxepnskabgrvuzrutgxttxdlbajvqpvdmbtatfc...
output:
913862
result:
ok single line: '913862'
Test #26:
score: 0
Accepted
time: 688ms
memory: 100216kb
input:
4000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1979531
result:
ok single line: '1979531'
Test #27:
score: 0
Accepted
time: 638ms
memory: 99688kb
input:
4000 fdhdijdfcdeedcbjgafdgcdegdbibaahdhaeifbdafhfhaefacigedcdhfbifdhbcjhaeidhdccdchicbjafceabjdchgjaabhbffgcajhdbecghdiehffjgiddhcfhdcabhhfigcdjihffagaibhjhhcdegiecbedabaajdgjbefbdbadcdeefgbibbhgaedhbhjgejchfjiididfcibjefhfgebiagfdfejjgbhdcfefghdafgjbbijaeciebghgcgiijhedeijahecfabgcbhefacbbaijdghdhe...
output:
1228665
result:
ok single line: '1228665'
Test #28:
score: 0
Accepted
time: 631ms
memory: 96532kb
input:
4000 rjdknocpagvrnghrpyukwifkkddprokianvndxdwgczcauhwrkpqmhqsmxqpmoxhazmujpspurtwndsfphxcrnwfnmuzauictvwfmowghscvvwckgzoxnkcawybzukbohyvtmrcwjgrgdvzovoosphzmirifzwmbfzuauwkmgoaodbfasvtjcuxmnftmcfohhkhdgtppkrfnvmpnhiwletasztebbskidtnjocaywgnrsdecnapsvpkuloxojjymelxtpyrlgfcakiexkurglbcwscmblkpqvmjlmcw...
output:
911422
result:
ok single line: '911422'
Test #29:
score: 0
Accepted
time: 572ms
memory: 93596kb
input:
100000 tduxfndk uneyosepeblysz myyzqqfxlyol hueyo vxkovfhrybgmvlhweq jkcclhdeyo dyggb mokfduurtqfsmaeynq gluuajukjnjc dfcjqnme xyrupyxgfnwd hvdjjbewg jjeyjmmlyol fiqebs otpjpq nfmezyyuyme wxyiuymslehvl coshvqaht tftlwgbnjyicrvjmuwrx owpmmwkqpvhwxhiujh vxrvymrouzryawtwombk ukkzjbon gokkrpnzmhonmhkfpj...
output:
989636
result:
ok single line: '989636'
Test #30:
score: 0
Accepted
time: 538ms
memory: 98516kb
input:
100000 baaabbbbabbabaaaba baabbaababbababbb bbbbbaababab baaabbaa abbabbbb baaabba baaabbbbbab bababbabbbb aababbbbbaabbbbabbbb abaababbaaaaabbb abaaabaaabbbbabbb bababaababbb aababbabbbbbbababba abaabbabab abbabbaaabaaaabbaaba abbaaabbaabbbba bbaababbabbaaabaaaa aaababaaabbbabb babbbb bbbbaaaabaabb...
output:
1282986
result:
ok single line: '1282986'
Test #31:
score: 0
Accepted
time: 496ms
memory: 96472kb
input:
100000 pkhvbtnxfvxaem uxvbtnxcgcsmwurthw rfvxaem wgzfvxaem fafvxaem nghhlpjfdga wcljhoesadwmfwhvbtnx uvbtnx bcbffvxaemvbtnx jhoesadwmfwhvbtnx ncgcsmwurthwvbtnx kyvbtnxjhoesadwmfwh wavbtnxjhoesadwmfwh ivbtnxssu qnghhlpjfdgarjw vbtnxibjhoesadwmfwh zfvxaemigqvbtnx swcgcsmwurthwsc sjhoesadwmfwh dfvxaemp...
output:
1170625
result:
ok single line: '1170625'
Test #32:
score: 0
Accepted
time: 704ms
memory: 92136kb
input:
100000 aaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaa aaaaaaa aaaaa aaaaa aaaaaaaaa aaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaa aaaaaaaaaaaaa aaaaaa aaaaaaaaaaaaaaaaa aaaaaaaaaaaaaa aaaaaaaa aaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaa aaaaaaaaaaa aaaaaaaaaaaaaa aaaaa aaaaaaaaa aaaaaaaaaaaaaaa aaaaaaaaaaaaa ...
output:
1950179
result:
ok single line: '1950179'
Test #33:
score: 0
Accepted
time: 964ms
memory: 97732kb
input:
20 cqhcbnnuobmgcqfdzbuvyajaidogyrtcjbemouifxulzlqcmtwiryttiwhpuykxjldvaxefuastnkvaeukxsdtdcauwbevkqziswmzrmrmabkchemhyrabtavqdajwzphqhuggbrujigzfhqxcrtcifvvvfgrevavfwdlauhjenkjudgyubcfhxcccivjfyemujywfhfjxsutvcsreuwnuypwimfqmlcjucfzklkhdeaahurnrqalqrjzfrrsctbzygaktltyrvyyqsnjinwyghzmyqgdmhekpeulrnjj...
output:
201946
result:
ok single line: '201946'
Test #34:
score: 0
Accepted
time: 835ms
memory: 101152kb
input:
20 baaababababababbaaaabababaaaabbabbaaabbbaabbaabaabbbabaabbbabbaabbbbabaaaabaabaabbbbaaaabbaaaaabaaaabaabbbbbbaaabbbabbaaaababbbbbbbaabbbababbabaababaaabbbbaabbaaaaababbbabaaaaabbaabababaabbbbabaaaaaababbabbbbabbabaaaabbaabaabaabaaaabbbbaaabbbbabbababbbabbbabaaaabbbaaaaabbbababbaaabbbbaabbbbbbabba...
output:
187803
result:
ok single line: '187803'
Test #35:
score: 0
Accepted
time: 987ms
memory: 98936kb
input:
20 wighspqotssudabkedkygymrryunfudbdlkxbdnwxfqbitnmwxmeyyypysfgoihtuuqxxgtullvvgjhcivigwiyucdatnkmhefgblbxymtusedwozhxxrvruaunngbxkifnvhkwvfqolvmawvxtnunjuhwjnzizioofvabqgtgtpvtnqshfmwoidmssmatwohblhdepwmjnhcbavkfjgwslikfumysdfwombscxfnnopqomcwyksqvaaaxoaprflgtmaxmfkbwcrkqtgodaeabgcyvepmjduervefcqgy...
output:
265680
result:
ok single line: '265680'
Test #36:
score: 0
Accepted
time: 740ms
memory: 99248kb
input:
20 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
1799368
result:
ok single line: '1799368'
Test #37:
score: 0
Accepted
time: 1124ms
memory: 100492kb
input:
2 aabaaabababbaababaaabaaaaababaabaabaabaabbbbbbaabaaabaabaabaabbbbbbaaaabbbabaabbbabaaabbaabababbbbbbbbaaabbbbbaabaababaabbabaaabbbbaabaaaababaaaabbaaaaababbabbbaababaaaaaabaababaaaaaaaabbbaaaaaaaaaaaaaabaaaaaaaabaabbbaabbabbabbabbaabbaabbaababaaabbababbbbaaaababbbaababbaabbabbbabaababaabaababaaaab...
output:
92934
result:
ok single line: '92934'
Test #38:
score: 0
Accepted
time: 1243ms
memory: 100324kb
input:
2 jcmgevxqwiaflstvldrnmkeoeczrruqbxfjdagtyptfcoyybepqqzvggxgxpcpsbubfxhyvyubbkbznfqdysyeywmxlrodslgxipyfougrgkstriwpavwatkzgbolwbrtjgtownxnthfoyqlqsimvbwuhakuwllrurllqakdwtlkrdvjvfvqiunruxlslwjhqwsgzcjvvwfpzdyxkwntqakmawglurskonqnpcknarecwezhaoasrmgrkmefgwpujijbmvqomwqjarsbguvxgcqrqwwwsnsexdhjazanvq...
output:
91737
result:
ok single line: '91737'
Test #39:
score: 0
Accepted
time: 506ms
memory: 97740kb
input:
2 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
93662
result:
ok single line: '93662'
Test #40:
score: 0
Accepted
time: 1188ms
memory: 97036kb
input:
10 cdvthwmepkhrkkvpucesqgrdwtzdvicynxrutfykridcsbrpfvhwdabzucdpkhpxhgtcospfashuvajdxqzarcclefcrosqvakyoenughdadgmgdchgvjiinpleddvbfhzuloqtvvtabfihkpnfaxqqmburgrslathljxehvahwhsftjszkpradswxaqrlqlvewukdpmlouftnomoydfajzzgzpxnhkilhcykskxiecburpkrtsuctvktkhitsqhzuflopjwwnysgneaiwumqpwlbetwwldxfiiuatqwh...
output:
735652
result:
ok single line: '735652'
Test #41:
score: 0
Accepted
time: 1160ms
memory: 99096kb
input:
4000 fcrfjdagkknhhvvklrmnnnqcrmjnifrphkwsnyaxiqfpnczytnngbejusuhabapjkodzmgwvydmlfomabzhedsywmhyohqzreeqqmpnkuawcoicrhlwndwjsehilzjfdnxwcmjmjjklzsptcbrpenaytjgfjpmmfjihyuvhfguhyjacktrrgrpadyhmptaueldcfzjkfdrfptizmbqvvixyiekxzmudxxgcwrpdxilmcvnqweltokrwqdtpsnvpndulujpttchxxvotzbppmilcmguewpvjupuoalku...
output:
555122
result:
ok single line: '555122'
Test #42:
score: 0
Accepted
time: 996ms
memory: 100672kb
input:
4000 abbaaabaabbabbbbaaaaaabaaaaaaababbabbaaabbaaabbabaaaababaabaaaabbbbbbbbaabaaaaaaaaaababbaababababababaabbabaabaababbaaaabaaaababaabbabbabaaaaaababaaababbabbbbabbbbaaaabaabaaaaabaabbaaaabbbbbbaaaaaaaaaabbabbabbaababbaababababbabbbbbbbaaababbbaabbbabaabbbbaabbbabaaabaaaaabbabbbbbabbbaaaaaaababbab...
output:
777185
result:
ok single line: '777185'
Test #43:
score: 0
Accepted
time: 409ms
memory: 97004kb
input:
2 baaaaaaabaaabaaaaabbaababbabbababbabbaabaabbbbbbbbabbbabaaabaabbbbbbabaabbaaabbbabaaaabbababbaabbbabaaaabaabbaaabaaabbbbabaabbbbababbabaabbabbabbababaabbabbbaaabababaabbbbbabaabbaabaaabbbaababababbaabaaaabaabbbbabbaababbbbabbaaabbbbbbbabababbaaabbbbaaabbaababababaabbbbaaabaaabbbababbbbbababbbabbba...
output:
54
result:
ok single line: '54'