QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110566#5440. P-P-PalindromeZeardoeAC ✓565ms160168kbC++203.7kb2023-06-02 20:55:372023-06-02 20:55:37

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-02 20:55:37]
  • 评测
  • 测评结果:AC
  • 用时:565ms
  • 内存:160168kb
  • [2023-06-02 20:55:37]
  • 提交

answer

/*
[templates]: 
duipai
spjdp
compre
addhis
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
mt19937 rng(time(0)); 
int rnd(int l, int r) {return rng() % (r-l+1) + l; }
#define watch(x) cerr  << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
    string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; } 
    reverse(s.begin(), s.end()); cerr << s << endl; 
    return;
}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍!
//use std::array.
map<array<int, 3>, int> mp;
int base[3] = {114514, 191981, 202009}, mod[3] = {1145141979, 998244353, 1000000007}; 
int powp[3][1000010];
struct PAM {
    int cnt, lst, n; string s; int tot; 
    vector<int> fail; vector<array<int, 26>> ed; vector<int> len; vector<int> pre[3]; 
    PAM() {
        cnt = 1; lst = 1; n = 0; fail.push_back(1); fail.push_back(1); 
        ed.push_back({0}); ed.push_back({0}); len.push_back(0); 
        len.push_back(-1); f(_, 0, 2) pre[_].push_back(0); 
        tot = 0; 
    }
    int getfa(int x) {
        while(s[n] != s[n - len[x] - 1]) x = fail[x]; 
        return x; 
    }
    array<int, 3> hx(int l, int r) {
        array<int, 3> ret; 
        f(i, 0, 2) ret[i] = (pre[i][r] - pre[i][l - 1] * powp[i][r - l + 1] % mod[i] + mod[i]) % mod[i];
        return ret;
    }
    void input(int l, int leng) {
        int r = l + leng - 1; 
        //tot += t.size(); 
        array<int, 3> tt = hx(l, r); //cerr << l << " " << r << " " << s.substr(l, r - l + 1) << " " << tt << endl; 
     //   cerr << t << endl; 
        if(mp.count(tt)) mp[tt] ++; else mp[tt] = 1; 
    }
    void insert(char ch) {
        n++; int p = getfa(lst); 
        f(_, 0, 2) pre[_].push_back(((pre[_][n-1] * base[_]) + s[n]) % mod[_]); 
        if(!ed[p][ch - 'a']) {
            ++cnt; fail.push_back(0); ed.push_back({0}); len.push_back(len[p]+2);
            int np = getfa(fail[p]); fail[cnt] = ed[np][ch - 'a']; 
            ed[p][ch - 'a'] = cnt; 
            if(len[cnt] % (len[cnt] - len[fail[cnt]]) == 0) {
                input(n - len[cnt] + 1, len[cnt] - len[fail[cnt]]); 
            }
            else {
                input(n - len[cnt] + 1, len[cnt]);
            }
        } 
        
        lst = ed[p][ch - 'a']; //tot += len[lst] - len[fail[lst]]; 
      //  cerr << "n = " << n << ", lst = " << lst << ", fail[lst] = " << fail[lst] << ", delta len(T) = " <<  len[lst] - len[fail[lst]] << endl; 
        
    }
}pam; 
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen();
    //freopen();
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int n; cin >> n;  
    f(_, 0, 2) powp[_][0] = 1; 
    f(_, 0, 2) for(int i = 1; i <= 1000000; i ++) powp[_][i] = powp[_][i - 1] * base[_] % mod[_]; 
    f(i, 1, n) {
        pam.lst = 1; pam.n = 0; f(_, 0, 2) {pam.pre[_].clear(); pam.pre[_].push_back(0); }
        cin >> pam.s; pam.s = ' ' + pam.s; 
        for(char ch : pam.s) if(ch != ' ') pam.insert(ch); 
    }
    int ans = 0;  
    for(auto it : mp) {
        ans += it.second * it.second; 
    }
    cout << ans << endl;
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
};

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 41ms
memory: 26992kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 30ms
memory: 26916kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 45ms
memory: 26956kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 42ms
memory: 27012kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

score: 0
Accepted
time: 72ms
memory: 42228kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

score: 0
Accepted
time: 67ms
memory: 42296kb

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

score: 0
Accepted
time: 203ms
memory: 95836kb

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

133586

result:

ok 1 number(s): "133586"

Test #8:

score: 0
Accepted
time: 183ms
memory: 64780kb

input:

3
abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbabab...

output:

118967

result:

ok 1 number(s): "118967"

Test #9:

score: 0
Accepted
time: 194ms
memory: 63428kb

input:

3
bbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabb...

output:

114444

result:

ok 1 number(s): "114444"

Test #10:

score: 0
Accepted
time: 187ms
memory: 63620kb

input:

3
abbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbabab...

output:

115321

result:

ok 1 number(s): "115321"

Test #11:

score: 0
Accepted
time: 234ms
memory: 95776kb

input:

3
azzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazaz...

output:

131825

result:

ok 1 number(s): "131825"

Test #12:

score: 0
Accepted
time: 62ms
memory: 29376kb

input:

3
yazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbyb...

output:

6

result:

ok 1 number(s): "6"

Test #13:

score: 0
Accepted
time: 55ms
memory: 29480kb

input:

3
azbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazby...

output:

6

result:

ok 1 number(s): "6"

Test #14:

score: 0
Accepted
time: 48ms
memory: 29388kb

input:

3
byazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyaz...

output:

6

result:

ok 1 number(s): "6"

Test #15:

score: 0
Accepted
time: 149ms
memory: 64340kb

input:

1
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabba...

output:

113382

result:

ok 1 number(s): "113382"

Test #16:

score: 0
Accepted
time: 95ms
memory: 60584kb

input:

5
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...

output:

123447499

result:

ok 1 number(s): "123447499"

Test #17:

score: 0
Accepted
time: 89ms
memory: 44404kb

input:

5
tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...

output:

25319820

result:

ok 1 number(s): "25319820"

Test #18:

score: 0
Accepted
time: 51ms
memory: 32696kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

2746507

result:

ok 1 number(s): "2746507"

Test #19:

score: 0
Accepted
time: 174ms
memory: 92424kb

input:

3
oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...

output:

1912677071

result:

ok 1 number(s): "1912677071"

Test #20:

score: 0
Accepted
time: 110ms
memory: 61844kb

input:

3
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxcxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

111259628

result:

ok 1 number(s): "111259628"

Test #21:

score: 0
Accepted
time: 71ms
memory: 38384kb

input:

3
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

13754174

result:

ok 1 number(s): "13754174"

Test #22:

score: 0
Accepted
time: 67ms
memory: 33928kb

input:

3
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

output:

1867151

result:

ok 1 number(s): "1867151"

Test #23:

score: 0
Accepted
time: 72ms
memory: 42468kb

input:

1
jjqjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjvjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj...

output:

1856484

result:

ok 1 number(s): "1856484"

Test #24:

score: 0
Accepted
time: 57ms
memory: 38108kb

input:

1
vvvvvvvvvvvvvvvvvvvvvvvvvvvqvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvsvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvnvvvvvvvvvvvvvvvvvvvv...

output:

190722

result:

ok 1 number(s): "190722"

Test #25:

score: 0
Accepted
time: 60ms
memory: 36972kb

input:

1
txxxxxxxxxxxxxxxxxxxxxxxxxxxxhxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxrxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxhxxxxxtxlxxxxxxxxxktxxxxxxxxxxxxxxxxxexxxxxxxxxxxxxxgxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxjxxxxxxxxxxxxxxxxxxxvxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxzqxxjxxxxxxxxxxxxxxx...

output:

76004

result:

ok 1 number(s): "76004"

Test #26:

score: 0
Accepted
time: 104ms
memory: 69260kb

input:

1
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

81149988

result:

ok 1 number(s): "81149988"

Test #27:

score: 0
Accepted
time: 146ms
memory: 71072kb

input:

1
llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

1272080790

result:

ok 1 number(s): "1272080790"

Test #28:

score: 0
Accepted
time: 195ms
memory: 94824kb

input:

1
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee...

output:

12890286923

result:

ok 1 number(s): "12890286923"

Test #29:

score: 0
Accepted
time: 104ms
memory: 46008kb

input:

5
dgasxxawfuzttbnrniddspiplejfqzzoadnogyemjktjqqjtkjmeygondaozzqfjelpipsddinrnbttzufwaxxsagdvkrreghjrkkrjhgerrkvdgasxxawfuzttbnrniddspiplejfqzzoadnogyemjktjqqjtkjmeygondaozzqfjelpipsddinrnbttzufwaxxsagdvkrreghjrkkrjhgerrkvdgasxxawfuzttbnrniddspiplejfqzzoadnogyemjktjqqjtkjmeygondaozzqfjelpipsddinrnbt...

output:

652993

result:

ok 1 number(s): "652993"

Test #30:

score: 0
Accepted
time: 91ms
memory: 45940kb

input:

5
jlpzojmatlmawicowbaazzfyzqdjodsyngoqfnxbshbjywkgafhdarnchbwcskosqxpdjffjdpxqsokscwbhcnradhfagkwyjbhsbxnfqognysdojdqzyfzzaabwociwamltamjozpljjlpzojmatlmawicowbaazzfyzqdjodsyngoqfnxbshbjywkgafhdarnchbwcskosqxpdjffjdpxqsokscwbhcnradhfagkwyjbhsbxnfqognysdojdqzyfzzaabwociwamltamjozpljjlpzojmatlmawicowb...

output:

425510

result:

ok 1 number(s): "425510"

Test #31:

score: 0
Accepted
time: 111ms
memory: 45988kb

input:

5
zwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqteylgwcwvfxzwzjeiveeviejzwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqteylgwcwvfxzwzjeiveeviejzwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqteylgwcwvfxzwzjeiveeviejzwzxfvwcwglyetqbpgxubiqntaydeqmdpassapdmqedyatnqibuxgpbqte...

output:

1180524

result:

ok 1 number(s): "1180524"

Test #32:

score: 0
Accepted
time: 116ms
memory: 45876kb

input:

5
rmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiqkdmpnzvkmqwgmrpocxxcoprmgwqmkvznpmdkqiiq...

output:

4551019

result:

ok 1 number(s): "4551019"

Test #33:

score: 0
Accepted
time: 107ms
memory: 45504kb

input:

5
tnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskksltnzbhxooxhbzntlskk...

output:

18042012

result:

ok 1 number(s): "18042012"

Test #34:

score: 0
Accepted
time: 106ms
memory: 45844kb

input:

5
wosalwxbdgvouchgnkqygjphbtpoxduzlpmpbuhhmwvgsbrfolbykyjzoukregdyxskkinjqzjeuublzpuukcaazbsggluyqlmyiallofjebbukuqcalufrqdjjkgvooretzaasgnpnztfalutzztulaftznpngsaazteroovgkjjdqrfulacqukubbejfollaiymlqyulggsbzaackuupzlbuuejzqjnikksxydgerkuozjykyblofrbsgvwmhhubpmplzudxoptbhpjgyqknghcuovgdbxwlasowovxg...

output:

61625

result:

ok 1 number(s): "61625"

Test #35:

score: 0
Accepted
time: 102ms
memory: 45324kb

input:

5
pyybsfiukgpneuwnykmxylcpaujvzpvcubdlvljkdwxkniwznzqvfblfedmydoqqrysksoobrwsqguocoxtfnisqmtbbieekshiwrzrbluflrtzfxwkvqtplcinkqqjsxogdsyucodbzhhnzaluymttfnzovqnevrqtbtqpmtgsfvnenstchzhdrequfxuasnkoxexafwpbgzqaobiicvmwugeugfgpmjvfphfojacdfhjplypqfoxzoacnfoucbhlqqnxxywfdaykxbsfkkkbwuryfwowvhecdgtnzcnp...

output:

57998

result:

ok 1 number(s): "57998"

Test #36:

score: 0
Accepted
time: 98ms
memory: 44520kb

input:

5
pndpupqzhnvxfilkpqdiabywphmclxjchfoctreacxnxwernjkhtyrgokfjpcuuqstsoserfmhfnrgdhzsioknvrhqflrjfkgkjrtoouchgeduceggstnsraurhpxgreryesioloxkcnndjdzyrfmksunizovolqltamzkmaggqftuvwjnkrhgyewthkqchdrgqrkwdfdwdoqunjulkpykaavlinxbzfuzzoqyvwrsfgmtvrzoyidesgkfwtbunicodseljtsxdzxpvpjnbaunefavrjjzhufqqsvekbpl...

output:

46840

result:

ok 1 number(s): "46840"

Test #37:

score: 0
Accepted
time: 107ms
memory: 148264kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

90000000000

result:

ok 1 number(s): "90000000000"

Test #38:

score: 0
Accepted
time: 67ms
memory: 29264kb

input:

5
nmnnmnnmnnmnnmmmnnmmmmmnnnnnmmnmnnnnnmmnmmmnnnmnmnmnmmmmmnnnnmnnnmnnnmmmnmnmmmmnmmnmmmnnnnmmmmmnmnnmmmnmmnmmnmmmnnnmmmnmmnnnmmmnnmnnnmnmmmnnnnmmmnmnnmnmmmmnnnnnnnmnnnmmmmnmmnnnmnnnmmmnnmmnmnmmnnmmmmnnmnnnmmmmmmnmmnnnmnnnnnmmnmnmmnmnnnmnmmnmnmmmnnmmnmnnnmnmmmmnmnnnmmmnmnmmnnnnnmmmnnmnnnnnnmmmmmmmnm...

output:

4526

result:

ok 1 number(s): "4526"

Test #39:

score: 0
Accepted
time: 58ms
memory: 28680kb

input:

5
aaupapuupauuauapupapauauuuuuaapauuaaapppuauuppupuapappuapuuuuaupappaauupapppuppauuaauppuappaappaupaaapaapupuuapaauuuppppuaapaaauuapupuaaapppuuaaapuuuapuaupaaapupaauaapuaapaaaaupuuuupupuapaaaapaupaaaapppuapapuauauapuaauuapapuappauauappuappppuppaauapapuapuauuapupaupaauauupaauapuaupauauuapaappaapaapp...

output:

2372

result:

ok 1 number(s): "2372"

Test #40:

score: 0
Accepted
time: 58ms
memory: 28876kb

input:

5
bkdbddddvddkvkvdbkvdvbbdkkkvvkbvbvbvvbvvvkdbdkkkdvbdkdkvbbbbkbbvbkddkbdvbkkkbdvvdkkdvkbkkdvddbdvdkkdkvbkkdkkbvddddvdvvkkvbbdvkkvkbkkkkkvddbbkdkbvdkbkkdvkvvvvkbkkvkbbdvbkdbkdbkvkkkkvkvkkvvkkvkbbvbvbbbvkbvbvkkvkvkbvbdvvdkkvdbkvbdvvdkvddvvddvkdbkbbvkbvdbvvdddkbdddvbbbdvvdddvdkbdkbkkdbvbkdvdddvddbkkvk...

output:

2339

result:

ok 1 number(s): "2339"

Test #41:

score: 0
Accepted
time: 51ms
memory: 26976kb

input:

2
afffafafaa
afaafaafaf

output:

29

result:

ok 1 number(s): "29"

Test #42:

score: 0
Accepted
time: 51ms
memory: 29008kb

input:

5
wjdulwwjulujdddljudwwlddduddujljjjdluljwddjuddddljwjuujdllllljuudddjwududddudllwudluldwudddwdllldlwwwdjlwuwwlddlluluwdlldjuudujdjujddwduwwjwlluudjjujjdudlljwdwduwjdljlwdjddwddddludwuuwlddddddljddlduddwldwddllduwjwddjdulwddjwddddwujwluujjjludwjddwwdjwddulldjwljudjljljduddjlddjujdddddudduljduuuljwul...

output:

2063

result:

ok 1 number(s): "2063"

Test #43:

score: 0
Accepted
time: 133ms
memory: 26980kb

input:

1000000
i
n
l
f
q
i
s
m
u
x
r
v
v
u
b
m
o
u
s
q
k
t
t
c
n
t
y
m
x
q
k
v
h
q
s
w
o
b
o
y
n
s
f
w
d
d
y
d
l
i
e
r
c
l
e
d
h
h
c
l
x
q
f
l
v
j
q
j
p
o
e
s
l
w
u
h
q
f
j
g
l
h
v
x
k
w
t
h
o
b
e
s
x
c
m
v
r
r
p
w
d
g
r
u
g
d
j
a
a
c
w
t
u
h
x
i
l
s
o
z
i
m
p
h
j
u
p
t
g
f
p
w
x
f
o
w
u
m
a
k
p
p
q
x
n
r
...

output:

26

result:

ok 1 number(s): "26"

Test #44:

score: 0
Accepted
time: 122ms
memory: 26976kb

input:

1000000
u
i
n
f
z
i
g
y
o
t
a
t
y
q
m
g
u
z
t
j
j
s
f
r
f
z
a
e
k
s
q
u
p
e
o
l
x
g
q
b
l
w
x
c
u
x
j
e
s
e
y
r
r
v
v
i
d
p
q
e
q
q
z
a
d
i
e
y
w
p
e
x
m
n
e
f
j
l
c
y
x
i
d
a
m
k
w
q
y
j
c
u
y
h
k
l
y
j
r
e
r
b
n
i
w
r
o
i
q
m
o
r
x
d
s
u
n
i
w
r
t
g
c
i
d
h
n
a
x
h
t
c
s
h
c
j
c
i
b
z
u
z
c
b
e
k
...

output:

26

result:

ok 1 number(s): "26"

Test #45:

score: 0
Accepted
time: 121ms
memory: 26968kb

input:

1000000
c
c
b
c
b
b
a
c
c
b
c
b
a
a
a
a
c
b
a
c
c
c
c
b
c
a
c
c
b
a
a
a
c
c
b
b
c
a
c
a
c
c
c
c
a
b
c
b
a
b
c
a
a
a
b
c
a
c
b
c
b
a
c
b
a
b
c
c
a
c
b
c
a
b
c
c
b
a
a
a
c
b
c
a
b
b
c
b
a
a
c
c
c
b
b
a
b
a
c
b
a
b
c
b
b
b
a
b
a
a
c
a
b
b
c
a
a
c
c
b
a
a
c
b
a
b
a
b
b
b
b
b
c
a
b
b
c
a
a
a
b
a
b
b
a
c
...

output:

3

result:

ok 1 number(s): "3"

Test #46:

score: 0
Accepted
time: 79ms
memory: 53600kb

input:

1
alngdzgfsplrmhhyblurpjxyqhrxmbyyubvvxtmuwrnfimiggwhsoluetintakqfohgtmtampxljpkawolbuyrsrmdjapecfytjcfxcdcyymbfaqshkujxxypteohceukrejaveenkmsdxrmpdlapcnsnowykiiqisgdratbqcwxfzspkglkqghmcsiqwemkilaisqucgithhcrjvoydpnmtmxdwsmjfjtimsqpvesagpqucssfwyricarvcpcujfsxupluoxxkzelyjqewsptiyobhrvdatjhbcohcdfd...

output:

3195

result:

ok 1 number(s): "3195"

Test #47:

score: 0
Accepted
time: 104ms
memory: 53580kb

input:

1
ghbhcdfhccifjigghcfhejhfcaibghfhehehjichadijbiihajddhgjgbdibecjjcaagedfaafejcfjjgdaiebcjihecjicadacefgbajeafccjdbafdjhjddjggbdhgdijbbiadeabbaiieacbeighagbaajgdbdajgajcabhcgfcadbadigjhehaibighhdjhaeggefhgfcfhaahhchedcjhbaedihgfgjiejeifbdieacghbghfjdjfehfgdfadeeghdjdcghibjdhiiggdchdbihfchbhchaeefccb...

output:

3395

result:

ok 1 number(s): "3395"

Test #48:

score: 0
Accepted
time: 106ms
memory: 53484kb

input:

1
fgffhhghheehgggfgghdeeeedgfdhdfehghhegeeggfhgdfhgfgedgdgdegedhegeedddefdfedhfgdhghehhggehdffdfgddhegeghefffgddedfeeggfheghhgghhhehfefhfegfgghfffdhfddgheegdgefdhhegfffefghhehgggheegdggddeggdehddhdfefgeffdgfdghefgegdhegdfggeggddhhddefghfgedhhdeghgfedhddefdhfhfdhfdghhegedfhdeefffegedddgfgefheffeeeedd...

output:

4178

result:

ok 1 number(s): "4178"

Test #49:

score: 0
Accepted
time: 94ms
memory: 35088kb

input:

100
xuxmuutatmmtxmautmmttuuaatmtamxmutxautxxttmuamtxaaumaautaaattmmmxumtxaaxmxxmmumuttmututmtmuauutuuuumtuaxmaaxattxattuuxumxtummmttmmutmmataxuuttattmatumxxatuxumatxutmtuuaaatxatutmmtutauauuuuxumataxtamauttaaxxuttaaxtauamammxumauxumuuutmuxmauxutuxuxtutmtatuxttxtummtxutxmaxuuxxtxuatuamuxaatuatuauxxmu...

output:

30276

result:

ok 1 number(s): "30276"

Test #50:

score: 0
Accepted
time: 106ms
memory: 35272kb

input:

100
wddldawddddlwwawawdwdldldldldawdwwdwaaddlddddadwladdddaddawadladlwldlalldddlddlddwdlwwddaddllwwdldddwwldddaadwadddddlddlwwdawawdwaawadadadldddwaaldadallwdwlwdlddadlddladdlddddaaddddlwwdaalddddwldaddadaddwawwalaalladdalllddadwddddadlwlddlddwldaadlwddwlldddadwwaddaaldddwwlddddddwddadddalwawddwdawd...

output:

30213

result:

ok 1 number(s): "30213"

Test #51:

score: 0
Accepted
time: 94ms
memory: 31328kb

input:

100
ygripyrkwoyooyykfppktyktktikoyyogttiorfyptgtogkygrtkiwgyoipkpkkiiikypgftggfpktrwoygfwptwpwfyptpwrwyigyokwprkfpkfkfwpfykrfygoyykkgfigyktyryrfpkfwoipoipotypiifpyooykkpokgopooykywyiwgoypwtwygfikorpoirptfffkwirriyyyypfpkiwrpyfgtwrtfyfotpttfrwpfoprftpyigfrtggpwifypwyfpowpripgtfrgkyirkrorfgrorwpopioig...

output:

16720

result:

ok 1 number(s): "16720"

Test #52:

score: 0
Accepted
time: 542ms
memory: 159924kb

input:

100
ywwcynkynntwwqtcyjcnkjtkwctnqwcttnnqwqjjqjjwykwwyjwnywkwqwnjytqkyyjwqwwycyycjtqyqyjyqqynqwwtnwcjwjckjnnywjwwjntnwwjywywwwkwwtcqnkqqjqqwkknnykjcynwnyyqwjwyjckkcnqyqwkywyykkwcwwwkcknkwttnqyqytnttyjqtwwywqyytywkcwyqnqwywwwtwywjwqjwcwcqwkqcqnywkkwyncjwtkcwqtjycywtjkywyknyjqcwqwtywqjktwytkcwykwknnwyj...

output:

346933

result:

ok 1 number(s): "346933"

Test #53:

score: 0
Accepted
time: 565ms
memory: 160168kb

input:

100
nmxxmmvdyyfnmmvmmunvmfmvrnddnryrmdrvuurmuvnmudnnrrmyvmvuvdxvyxvmumnnrxummffuvdrmxnydfxnxfnxmnvmyfnmuyxruxfymyryunrmfmdmmxmufnmmmmmryrnfmrrvrfvfdxumymxmmxmxxmnfyddmmurvfvumfmxrmvfmnxnmnrvmyxfyrvnyfyyvvrmryynruyxmfmvmxxmrxrvmxudyvfxndrnvunvmnyxvyfvvxrndmffdvrfvfmmufdumxdvmumvmmxnmxdudyyfrdvmrxvyyx...

output:

354764

result:

ok 1 number(s): "354764"

Test #54:

score: 0
Accepted
time: 305ms
memory: 94692kb

input:

100
hohohoohoohhoohhhhhhohohhhooohhohoooohohhhoooohohhhoohhooohhhooohhoooohooooooohohhhoohohohhhohoohhohhohhoohohhhohohoohhhohooooooohoooohhooohhhooohhoohhhohoooohhhohoooohohhooohhhohohhhhhhoohhoohoohohohhohhoohohhhohohoohhhohooooooohoooohhooohhhooohhoohhhohoooohhhohoooohohhooohhhohohhhhhhoohhoohooh...

output:

400202791

result:

ok 1 number(s): "400202791"

Test #55:

score: 0
Accepted
time: 285ms
memory: 93456kb

input:

100
yyyyyjyyjjjyyjjjjjyjyyyjyyjyyjyyyjyyyyjjyyjjjyyyjyyyyjjjyyyjjyjyyyyyyyyyjjjyyjjyjjjyyyyjjjyyyyjyyyyyyyyyyjyyyyjjjyyyyjjjyjjyyjjjyyyyyyyyyjyjjyyyjjjyyyyjyyyjjjyyjjyyyyjyyyjyyjyyjyyyjyjjjjjyyjjjyyjyyyyyyyyyyjyyjjjyyjjjjjyjyyyjyyjyyjyyyjyyyyjjyyjjjyyyjyyyyjjjyyyjjyjyyyyyyyyyjjjyyjjyjjjyyyyjjjyyyyjy...

output:

200209587

result:

ok 1 number(s): "200209587"

Test #56:

score: 0
Accepted
time: 332ms
memory: 93508kb

input:

100
coppocpcpccpccppocopcooccopopccopccocccpocooccocpcppccocoppcocoppcoocoopopoooopppopppoccppccpcppccoccoccppcpccppccopppopppoooopopoocoocppococppococcppcpcoccoocopcccoccpoccpopoccoocpocoppccpccpcpcoppoccoccppcpccppccopppopppoooopopoocoocppococppococcppcpcoccoocopcccoccpoccpopoccoocpocoppccpccpcpco...

output:

203651

result:

ok 1 number(s): "203651"