QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#924480 | #10114. Anthem | SurfCoffee (Anton Stepanov, Alexey Vasilyev, Vladimir Novikov) | AC ✓ | 93ms | 117212kb | C++23 | 3.9kb | 2025-03-03 01:33:37 | 2025-03-03 01:33:37 |
Judging History
answer
// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
// #pragma GCC target("avx,avx2")
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (n); i += 1)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(a) ((int)(a).size())
const ll inf = 1e18;
mt19937 rnd(234);
vector<int> manacher(const string &str) {
int n = str.size();
std::vector<int> odd(n);
auto ¤t = odd;
for (int i = 0, l = 0, r = 0; i < n; i++) {
if (i < r)
current[i] = min(r - i, current[l + (r - i - 1)]);
while (i - current[i] >= 0 && i + current[i] < n && str[i - current[i]] == str[i + current[i]]) {
current[i]++;
}
if (i + current[i] > r) {
l = i - current[i] + 1;
r = i + current[i];
}
}
return odd;
}
string remove_same(const string &s) {
string t;
t.reserve(len(s));
for (auto c : s) {
if (t.empty() or t.back() != c) {
t.push_back(c);
}
}
return t;
}
struct node {
array<int, 26> go;
int link;
int ln;
};
string compress(string s) {
string t;
vector<node> g;
auto new_node = [&]() -> int {
int v = len(g);
g.push_back(node());
g[v].go.fill(-1);
g[v].link = 0;
g[v].ln = -1;
return v;
};
int root = new_node();
int cur = root;
vector<int> nodes(len(s));
for (auto x : s) {
if (!t.empty() and x == t.back()) {
continue;
}
t.push_back(x);
while (cur != root and (len(t) - g[cur].ln - 2 < 0 or t[len(t) - g[cur].ln - 2] != x)) {
cur = g[cur].link;
}
if (g[cur].go[x - 'a'] == -1) {
int to = new_node();
g[cur].go[x - 'a'] = to;
g[to].ln = g[cur].ln + 2;
if (g[to].ln == 1) {
g[to].link = root;
} else {
int link = g[cur].link;
while (link != root and t[len(t) - g[link].ln - 2] != x) {
link = g[link].link;
}
assert(g[link].go[x - 'a'] != -1);
g[to].link = g[link].go[x - 'a'];
}
}
cur = g[cur].go[x - 'a'];
nodes[len(t) - 1] = cur;
int v = cur;
while (v != root) {
int ln = g[v].ln;
int i = len(t) - (ln + 1) / 2;
int u = nodes[i];
bool found = false;
while (u != root) {
if (g[u].ln == ln) {
found = true;
break;
}
u = g[u].link;
}
if (found) {
rep(k, ln - 1) {
t.pop_back();
cur = nodes[len(t) - 1];
}
break;
}
v = g[v].link;
}
}
return t;
}
string remove_start_palindrome(const string &s) {
auto odd = manacher(s);
int opt = 0;
for (int i = 0; i < len(s); i += 1) {
if (i - odd[i] + 1 <= opt) {
opt = i;
}
}
return s.substr(opt, len(s) - opt);
}
string solve(string s) {
while (1) {
string t = compress(s);
// t = compress2(t);
if (t == s) {
break;
}
s = t;
}
string t = s;
t = remove_start_palindrome(t);
reverse(all(t));
t = remove_start_palindrome(t);
reverse(all(t));
s = t;
return s;
}
int32_t main() {
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int _;
cin >> _;
string s;
cin >> s;
string res = solve(s);
cout << len(res) << "\n";
cout << res << "\n";
return 0;
}
/*
9
acwrwcwra
*/
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
input:
14 ecerrcwrwcwror
output:
7 cercwro
result:
ok correct answer
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1 a
output:
1 a
result:
ok correct answer
Test #3:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
10 opopotopoa
output:
5 topoa
result:
ok correct answer
Test #4:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
25 fghxabcdeyedcbaxabcdeylkd
output:
13 fghxabcdeylkd
result:
ok correct answer
Test #5:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
15 abfgfgfgfgfgfkl
output:
7 abfgfkl
result:
ok correct answer
Test #6:
score: 0
Accepted
time: 1ms
memory: 6880kb
input:
500000 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
1 x
result:
ok correct answer
Test #7:
score: 0
Accepted
time: 5ms
memory: 6880kb
input:
500000 vffffvfvffffffvvvvvvvfvffvvvfvvvvfvvfffvfffvvvvvvfffffvfvffffvvvvffvffvfffvfffvffffvvffffvvfvfvffffffvfvvvfvffvvvvvvvfvfvfvfvvvvfffvfvvvvfvvvffvvvfffvvvvfffvvfvfvvvffvvfvfvfvfvfvfvffvvvvfvvvfvvfvvvvvvvvvfffvfvvvfvffvffffvvffvvvffvfvvfvfffvffvfvvfvvffffvvfvfvvvvvvvvvfvfvvvvffffvvffvvvffvvfvfvv...
output:
2 fv
result:
ok correct answer
Test #8:
score: 0
Accepted
time: 7ms
memory: 7368kb
input:
500000 jjhhheehejhhjeejeeejejhjhhjehhehjjheeeehjhehehjehjhhhjejjheejjjehejjejejjhjhjehjhjheehjehehejhhhjhhjjeeeeejhejjhhjjehjhhjejjjhjehjeeejjhehhjejhehehhehhhjjjejehejjjejjjeehhhhhhehjejjjehehjjhheehhejhehejejhjehehejjejjhheeheeheehhheheeejjhhhhjjjjhheeheeehhehhehhjjjjehhhejjjhhhjehhhhjjhjhjhheejhh...
output:
955 hejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhejhe...
result:
ok correct answer
Test #9:
score: 0
Accepted
time: 13ms
memory: 7776kb
input:
500000 yfssssssysfsyyjjjssyyyyjyjjysfyysfsjyjyfjjfsysssjjfjjfsysffsfyffyjyfyfssfsffyjffjjyffsfjyjfjffysyfjsyffysjssjjyyjysysyfsssysjsjyyjsyysyffsyyyjjsfjfsyjsfyyffjjsjjfsffyyyyffsjyssffyyffjfsfssyyjsfyyyyyfsjysjfsjyyssffjyjsyjyyssssfffssjfffyyjsjsyjfjsfjssjsfysyfjsyfsjfyjssjssfsjffyssfsffsyyfjyssfjs...
output:
296116 yfsyjsyjysfysfsjyfjfsysjfsysfyjfjyfsfjyjfysyfjsyfysjysyfsysjyjsyfsyjsfjfsyjsfyfjsjfsfyfsjysfyfjfsyjsfyfsjysjfsjysfjyjsyjysfsjfyjsyjfjsfjsfysyfjsyfsjfyjsfsjfysfsyfjysfjsfjsjyfsjfsyfsjfysfsyjysfyjfjsjfjysfsyfjsfjfsjyfsfjsjfsyjsjfyfsjysyjsyjfsjysfsyjfsjfjyjsysfyjysjfyjyfsyjsjyjfjyfsyfjysfyjfsjsf...
result:
ok correct answer
Test #10:
score: 0
Accepted
time: 15ms
memory: 7900kb
input:
500000 nrnrtnnnrwmtwnnrnmtmtrrtwrmrtnrrwwrmrntnrrmnttmrwnmwttmrwrmnmntnwmmnnnrrwrttnwtnrwtnrrtmmwrwnrnrrtmwwrrrtntwntnmtmmtmrtrnwnrrmrrrnrwwwmrttnmtrrnrrrtrnnnrmnrnwrnmrrrnttmntrnmnmmnrnnnnwwtmnwrwntwwmnmrmwwtnrmmrtmrntmrnmtmtrtrmntmwwmwwtrttrrwnrttntwrnwwtmrrwntnrwnttwmnntnmnwttmnttnnntwnwntrmmnnww...
output:
354103 nrtnrwmtwnrnmtrtwrmrtnrwrmrntnrmntmrwnmwtmrwrmntnwmnrwrtnwtnrwtnrtmwrwnrtmwrtntwntnmtmrtrnwnrmrnrwmrtnmtrnrmnrnwrnmrntmntrnmnrnwtmnwrwntwmnmrmwtnrmrtmrntmrnmtrmntmwtrwnrtntwrnwtmrwntnrwntwmntnmnwtmntwntrmnwrwtrnwtrmtwmrntwrmtwrtwtmtrwrmtmrtmwmnrwtnrnwnmrwmrnrmtwmtmrwntmrnwmrtrwtnmtrmntrmtnmnw...
result:
ok correct answer
Test #11:
score: 0
Accepted
time: 12ms
memory: 7904kb
input:
500000 mgwhjnttgmhvhjppjngrgjmggnnphptjtpghtjjrgwmhwjjhgwghthtvtnhrmtmgpwpvvtwjmpwjmppvrhnpwtptggjrwwppgvmvnmjthvhrjhgvptnmgghpggmgwwwrgjvmhvggmppgjpmmtghtpmnpmhgpgmjvhmjgtrtrhmgtmmtnwvrtwpwmvwwhthgrwwvtphrpjhgtvrpthvhvgvghtjhwnhwnvgjjgpwtpvjtvwptwnjrggntjmpnmvvwrtmvtrmwjjrmvjttmjwmntvprhmmnwnpwjptt...
output:
439545 mgwhjntgmhvhjpjngrgjmgnphptjtpghtjrgwmhwjhgwghtvtnhrmtmgpwpvtwjmpwjmpvrhnpwtptgjrwpgvmvnmjthvhrjhgvptnmghpgmgwrgjvmhvgmpgjpmtghtpmnpmhgpgmjvhmjgtrhmgtmtnwvrtwpwmvwhthgrwvtphrpjhgtvrpthvghtjhwnhwnvgjgpwtpvjtvwptwnjrgntjmpnmvwrtmvtrmwjrmvjtmjwmntvprhmnwnpwjptwjprjnwnrnwnhpmvwgrvhrvwpgvgjwvrjgvp...
result:
ok correct answer
Test #12:
score: 0
Accepted
time: 10ms
memory: 8032kb
input:
500000 wqzljqzpgmeygcslzjnjshzcqebrgpsedikdmsgnrprhrskqshnerzuezakupnijkubmszgziskupkqselghcbjnoflwqszpggusmkhycsbvxpewveflohuhmhegpkpxektfetegakdgkjoomdahijbntcfiuerlwfnvzzmmnhikxcagigmvhzeafaceiekrtebopmamgkpevwqiymknrtxwoygnlnyudorweisridwdslnqcdgsofvjhghotiabhivcpetvwezmqkctetzprrnmueleehbvjautb...
output:
479153 wqzljqzpgmeygcslzjnjshzcqebrgpsedikdmsgnrprhrskqshnerzuezakupnijkubmszgziskupkqselghcbjnoflwqszpgusmkhycsbvxpewveflohuhmhegpkpxektfetegakdgkjomdahijbntcfiuerlwfnvzmnhikxcagigmvhzeafaceiekrtebopmamgkpevwqiymknrtxwoygnlnyudorweisridwdslnqcdgsofvjhghotiabhivcpetvwezmqkctetzprnmuelehbvjautbulqcei...
result:
ok correct answer
Test #13:
score: 0
Accepted
time: 5ms
memory: 10708kb
input:
500000 uuurruuuurruurssruuuurruuuurssruurrrruurrrruurssruurrrruurrrruurssruuuurruuuurssruurruuuurruuuurruurssruuuurssruuuurssruurruuuurruuuurruurssruuuurssrrssrrssruuuurssruurruuuurruuuurruurssruuuurssruuuurssruurruuuurruuuurruurssruuuurruuuurssruurrrruurrrruurssruurrrruurrrruurssruuuurruuuurssruurr...
output:
947 fksqwywkgmsaukjhmljmkmtwxzhpntmaupdcxvevnpkwcksfpvgjoplgybafnyxiqetexhsrygzuzqshgpdazxmpqbhaencwvdreyrwxuyvwjduvlougsqouawhzbitursdiqoqclfvxcrqabfnufynzjgzkwrgmogrargbdfgdywvhfbltgnjbrfsxhljwynytemwsmucfckptusmwkmtjeizyvatnyjtfikedfapwahpivjvcdtvysqdpsdhewuykhmqiewtcyhkdhszirsvugszhdmaitpxmuaync...
result:
ok correct answer
Test #14:
score: 0
Accepted
time: 7ms
memory: 14580kb
input:
500000 qdudvkgsaquhcykmrdmbagyjdnepbbwwfqvsjltzbfskloqsxfuhhtbzzwtojrndqflqqzirnfototshsnhkbeknviidotetluvftzcjwkqusyqkclumbzkmcweznjyunjlypanljsjvqniccmzgxsjcpwhakbnohvykqeduoamqxewhtvpqjtuhryvvqhltqkwcihmohxikeizbkcvdxriecurbebhtzxozsfnwcbhvepmucmikjvufofxmlevlmlvelmxfofuvjkimcumpevhbcwnfszoxzthbe...
output:
954 qdudvkgsaquhcykmrdmbagyjdnepbwfqvsjltzbfskloqsxfuhtbzwtojrndqflqzirnfotshsnhkbeknvidotetluvftzcjwkqusyqkclumbzkmcweznjyunjlypanljsjvqnicmzgxsjcpwhakbnohvykqeduoamqxewhtvpqjtuhryvqhltqkwcihmohxikeizbkcvdxriecurbebhtzxozsfnwcbhvepmucmikjvufofxmlevlmuhdseiamswxoposjgspkoeagmhytsftrdwiudsfquisqzjbav...
result:
ok correct answer
Test #15:
score: 0
Accepted
time: 3ms
memory: 7436kb
input:
500000 yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
956 irhqydegmplfcfszlavghwutgwbqzicmflchlkaiywqcqtihghwxefgdmecfeimiunjmvzkeajiyvbczcymfcblbnwhdvcdqfpadnjrplxncwesxlaljgptfaelbfvsumskzmbjusbrapbtnwbkwdbvnxhozshgpugaclcqdtbefsdhjyrvqltvpfbzyaltnqyhzwykjxgxycdgbwrseqacnvigtodjxdgravsdkcozxhwdclvovncsuxrcgruevqejyxfxpugowxboyxnqxruxdfoibdwsbtscdwram...
result:
ok correct answer
Test #16:
score: 0
Accepted
time: 2ms
memory: 8524kb
input:
500000 ppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...
output:
952 gtjzfkctpvfawxvoysyvbgmjquwcywzyvpswliuflulkufjzmwevlmiezldjlkdudxtnjgfydslfnadvrztqrusbuksowybwkybsbzcmqahyfnfsamcbqnpxqkxpmypahzasjewbureninthnupmckmivscuogvwbkbzkvehpscfijaxbyxrliymespfxjlpheaigfkrsuvrwcytjdbyoxlylhvefltiuyovyjuwaemcgsyldenaokrwawfjcrvatfnpqsrytuvnqyquxzcsxgdpiajmuqdznuczncmb...
result:
ok correct answer
Test #17:
score: 0
Accepted
time: 6ms
memory: 8620kb
input:
500000 cccppcggcppccccppcggggcppccccppcggccggccccggccggcppppcggccggccccggccggcppccccppcggggcppccccppcggcppccccppcggggcppccccppcggggcppccccppcggcppccccppcggggcppccccppcggccggccccggccggcppppcggccggccccggccggcppccccppcggggcppccccppcggcppccccppcggggcppccccppcggcppccccppcggggcppccccppcggccggccccggccggcpp...
output:
598 ygpgcgpycpcgpypcgpycpcypgcpcycpycgcpgcypgcygpygcygpycpcgpcpycpygcgpycgypgpcypgypcgpgygpcgpcpgycpypcygcgycpypcypycgpgypcgycygpgypycpcypygpcpypgpypcgpygcygcygpgcpygpcycpgypcypcpygpcpycpygpcgpycpcygypgcygycpgypcypycgypycgypycpycpcgygpcycpcgcpycpycgypycpygpgygcpycpygcgpygcypgpycpgpcycpygcygpygcypgcy...
result:
ok correct answer
Test #18:
score: 0
Accepted
time: 6ms
memory: 8584kb
input:
500000 gdggggdggdggddddggdggggggggggdggddddggdggggggdggddddggdggggggggdggddddggdggggggdggddddddddggdggggggdggddddggdggggggggdggddddggdggggggdggddddggdggggggggggdggddddggdggdggggdggdggddddggdggggggggggdggddddggdggggggdggddddddggdggggggdggddddggdggggggggggdggddddggdggdggggdggdggddddggdggggggggggdggddd...
output:
708 xgmxdgxdmgmdgmxmgaxgmgdxmagxmgxmxgaxdamgxamdmgxdxgmaxdmdxadgxadxadmamxaxdamxgmxdmgxmxadmdadgagdxaxgdmaxdmxdxmdgdmadxmdgmgxmdgxdaxagdmgadgaxgmdgmagxmdgxmamdagmgxdgdmdxgdagdxadxdamadgxmagxgdmgxamagdmxaxgadxdgmxmdgagxdxmgdxgaxmdmxmagdmgdaxagmdgmadxdmdamgxadxamdamgaxgaxmgmxamdgaxdmgmadagmdxmdxgadxda...
result:
ok correct answer
Test #19:
score: 0
Accepted
time: 9ms
memory: 10832kb
input:
500000 smmmmssmmmmssmstmmtsmssmstmmtsmssmmmmssmstmmttmmtsmssssmssmssssssssmssmssssmstmmttmmtsmssmmmmssmstmmtsmssmstmmtsmssmmmmssmmmmssmstmmtsmssmstmmtsmssmmmmssmstmmttmmtsmmstmmttmmtsmssmmmmssmstmmtsmssmstmmtsmssmmmmssmmmmssmstmmtsmssmstmmtsmssmmmmssmstmmttmmtsmssssmssmssssmstmmttmmtsmssmmmmssmstmmt...
output:
868 kqvmqrtmqsmstmtqkrqvmvqkvrslkvskvqtzlvtqwklsmwsvsztvqsmwsrskvlqmtzmsqkmtmqszkwmlqsmskwsrlstrlvkvmlwstqmwsmkwmtqsrzqwkrlrkwvlmkzmklwmrwzsrzstmklkvrqvmzvrzkzwtmzlqslsqtmtzklrtmwlslvtzlmsqwlwrlztqvrtswvkvqrsmrzslmqrkvzqzrmkvmkslrwzkmtslmzmlzwlqvqwmsklzkwlvkqrsqmtmltkzsvzskqwmtkrvwklstwlqslmlrqtszkm...
result:
ok correct answer
Test #20:
score: 0
Accepted
time: 11ms
memory: 22364kb
input:
500000 prqddgelpjqczwzxxfgqqgfxxzwzcqjplegddqrparbfyldecnfpffeodfhqzjgqiubxkdfcmhhhttmivxmobcfevxuejadsapwvrqimionlfiysoguynaamfizkapcpwdayyadwpcpakzifmaanyugosyiflnoimiqrvwpasdajeuxvefcbomxvimtthhhmcfdkxbuiqgjzqhfdoeffpfncedlyfbraprqddgelpjqczwzxxfgqqgfxxzwzcqjplegddqrparbfyldecnfpffeodfhqzjgqiubxk...
output:
9585 hnxcrxidteamdpiuskevucmfknjenmocasjtcbhoryvhzmtfrsaeuhihjdgevqbsjwpmxwmgowncdwzszvlwapubpxczpxjaxgsqtwozgojdrvzkgnacocfmzubmsursdvsoewbrqgtwynjmfmziywbslywnpjianhnevwmibolvkhtowatqdozejlhvmganftbiwodoalkpdjnoxmqecywgjldadxckyjhwcagoxlupolcivnsrcgwoknaqnpmjztntoiaefcxcyizcydyebxrijyqafozysdipmfa...
result:
ok correct answer
Test #21:
score: 0
Accepted
time: 2ms
memory: 9216kb
input:
262143 uuuuhhhhuhqwqhuuhuhqwqqhuhhhqwqwwwwqwqhqhqwewwwwewwqqhhhqhuhuuhuuuhuhhhuhhhhqhuuuuuuhhhhqhuuhhuueuevevqqveeuuhqqhhhqwweeeepppeeepeeweepwpeewwqhqqhqqweepepeepwwwpewewwwqwwepewewqhuuhuhqqhqhqhhuuuueuuuuuueuuuhqweppewqqwqhhuhuuuuuuevveevqvqwwqwqvqvvqvevveuuuuuuhuuevqwqvvqqqvqwqvqqqvqqqqwqwwwvppp...
output:
932 wlpvhmqmduldmudqmpmuqelwlpvqplvdlvewdpvudulhvumdleqpqhqlwpwhmupudvemdmuplwdhuwumvuwqhpeuvuhwdvhulwumvmumpulwluhpvudwpewqhuevqwvpldvpuwhluvpvhuqpeqdwdudwlqwudvuhuvhwevedemehvevhpmewpuvpdwvqudqmuwdmuehvmheqwqpmuwuqluepupvwvpelwvpedqmqlwpumdupqepuvweqwhvehqlhlwhmpqdmdueqmdlulmlumewuqvplpwuvhdqvlvhu...
result:
ok correct answer
Test #22:
score: 0
Accepted
time: 5ms
memory: 6972kb
input:
262144 szszttzzzztgttgttggttgggttttztzzzztgzzzggttggtgzgtztggzzggzwwwwzwwwgdgddjjddjjdjjrrrrrwwrrrjrwgwwwwrwgwwgwwgwrjrwwwgwwgwgwgggwggwwwwwrwgwwvvvvvqvqqqqqmqmqqqqqmqxdvvvshsvvvdxdvvdvddvdvvsvvdddxdvvvdvdxxqxxxdvvddxdxdxqxqqqqmqqqqqqqqqmmqmmmmqmqqqqqvqqmmmmqqmqxqqmqqqvvqqqqqqqqqvqvvqqqqqqqqqmqxxdxx...
output:
481 thjgwsmsyutgtzxsxjrwhtqxzjxdutsvzxjxvhwruhtwgzgqutdhmjgjhrxmvdutzysdsxdmsztxwxmzsxdxvgwhjmvwvzdjmwxgmzwjqrzvmjtwxsvtuwjgtzvtxmjysytsgywtztyhsvtzuwysztgzwgdjrwgwvqmqxdvshxmvwsudtzyhzdyzqrdrjxyvdqjxdsuyqrsqgrwzdmurduxwrjrurqumdtygzwswuvwzvxzdymzmgwmgjsxzhdmwvgdthmxyhsvuxgsmsvygrxszwtdtxdyvqxyhxrvj...
result:
ok correct answer
Test #23:
score: 0
Accepted
time: 6ms
memory: 9088kb
input:
262145 aaadaddaeaeaeeeadodadooqoqqoddaaeaaeeaaaadaeaeaewewwwvvwvwewweeadoqlllqodaeewewewvviiizhhzzhziizizzhhihhhhhziiivivizhzhhziiiiiiizhhhhhhziziiizzizhzziziivvvwviizhhihhhhzizzhhhhhzzizhhhzzzzzhhhhiihihhhiihihhhihhhhhhhhhiiiiiiiiiihhhzzhhhiiiiiiiihhhhhhhiiyiihiiihhhhzivvweweeeeeweaddodoodaddodoqlq...
output:
688 bklavoulcrymgkqyibmcgthzcmewopwgfteqflxedrtqblicmtzjhgadoifdwanmnuyceimwlizakodkitbaqkctbsjlgmpgwmeouwrnfxiruzhcreauofjbabydkwswjfomczurbjpawbyuithsofxqesofqsyqublzvkpgsynmqugtcdjbtsjiulbfmhpixuxdwbzwtbzqlqodaewvizhiybpnaurgxdfxbiwszpgizdrqwnjvuroxiwqpdgqcuczkrqkscudpxonzsviqwjbykxcovmjzlhqanykz...
result:
ok correct answer
Test #24:
score: 0
Accepted
time: 8ms
memory: 8596kb
input:
499999 fffaaaassssafszssffszszaasisiisiisazassaaaassieiiieeteiieeieiisisieteieississiiisisisieeieieetttetttbbbbyyibiyybbtettttetbbtteeeieeeietttetteiiisasiieiissazaasasiieeetbbbbbyybbtteietbybttbyyibbiibibiybybbtbtttteisieieieetbttbtttetbtteeetbtetetbttbteeisiietetbttetbbbtbbtbbybbtteiiisiiieetbyybb...
output:
238 gtymyaleytafblcxzflailetsmgftyetgcigsmsdbfmbxbgyagtcesdaxlyzamcsdlmctbmbtglybltlelmyslgcfsztfifxtalgazatcextlzbylybsilbmemcfelbzidtfzsftgaxtbzadezgldcbdmtldtdlexeslgxdiabgsfybtyxymaiscdxtdagmlfyagmitfgltzygbiybteisazsfasiegalcmacemxlfxtyx
result:
ok correct answer
Test #25:
score: 0
Accepted
time: 9ms
memory: 14504kb
input:
499999 ddqdqdqdddqrnnnrqqqrrqrnrnrrnrqdqdqqqfttitiixixgggxgxxxxittffqdddqdqddqrnrqqqddqdqqqdqqddddddqrqdddqqdqdqqdddqqqrnrrrrqdqdqrnrnnrnrrqqrqdqdqqdqddqqdqdqdqqdqrrrnnsxekexxxsxsnnrrrnnnrrrnssnrrnrrnnrrnsxxssxexsssxexexsnrrnsxexxxsssxekpuupuppvpupuppuppuppuppupupupppkekeeeexsxekekppppkexxxeexekppke...
output:
836 qmjgfzxitaoukagvsebiakboyvqnfhwlneyxflnehiucnbrhsyqymardyormfupyvjyushrgldwjuzsygwkvznjibormsdpkzyxlbmopkobgxfpfbsfuyaxupthitwdijsiyeungjhtvwynrkduvpupkexsnrqdqftixgdjbsnibtprmbygzpkpsiaxgrisguvxfhwmahjsirtdmizbtlkdvtoxsytbfscvesrprzifpsuvecsgtvlhxkrbtejsqpelwbsiydlwzthjljqeafcplgpmqatvhtbadszhp...
result:
ok correct answer
Test #26:
score: 0
Accepted
time: 7ms
memory: 6704kb
input:
500000 nttttttdnddddnnddttttnntnnntnndddnddnnnnnnnnnnttttnttttttdtttttttttntnnntntnttntttntttnttdtdtdtttnttttttttddtdtddtttdtttttttdtttttdtdnnddntttntndttdtdntntntnnnttnddndtttttdddntndnttnntntnttnndtttdtddtdtdttttdtttttdtdtdddttntttdttdtddtdtdtddtttdddtdddtttdntntndndnntnddntndnttttndtttttttddtdddd...
output:
10 dntdntdntd
result:
ok correct answer
Test #27:
score: 0
Accepted
time: 8ms
memory: 6752kb
input:
500000 tttttdtdttttttttttttttdtdtxxxxtxxxxxxxxxxxxxxxxxxttxtdtdxxxxxxxxttxxxxxxxxtddtdxdtxxtdtxxddxxxxxxxxxxtxxxtxxxxdddttxxtdtddxxtxxddxxtddxxdtdddddddddddddddddddddtdtddtdttttddtdtdddddddddddtdtttddddddddddddddtdtdddtdtdddtdxdxdtddtdtdddxdttdddddtdddddddddddddddtttddxxxxxxxxdtddddddttdttddddtddddd...
output:
34 xtdxtdxtdxtdxtdxtdxtdxtdxtdxtdxtdx
result:
ok correct answer
Test #28:
score: 0
Accepted
time: 8ms
memory: 8504kb
input:
500000 zizdddeeedzzdeeeeeeeieezeeeieeeeiieeieezezeeezeiieeeiieiiiieeeeeeedeeeeeeieedzdeeieeeiieieiieeeeeeeeeeiieezeieieeeeieeeeeeeieeeeeiezzzgzzeeezggggggggggggzdgeeeeeeieeeeeeeeeeiiieeieiizziiiiiieegegdzdzzzddgeeeeeeieeeeeegdzzgggggzeeeieeedzddziizdzdziigzeeezgzzggiggggigzzzezzeeezzeeeeddididdidedd...
output:
185 zegedeigdzdegezegzdzizdzeizediziezidgizgzdidezgizdeiezgzdgeizdziegieizigiezgdedizegdzezdgzdezigzezdeiedzedidzezdigidizgdegzeiegzizdgigezdgzdeidzdgeidigzdgzedgdzgedegdgzdzizegdgzdiedidgi
result:
ok correct answer
Test #29:
score: 0
Accepted
time: 10ms
memory: 10812kb
input:
500000 tioqooqoittitiitttitkkkiwookhwkwwwwhhkkhwwkkwwwkkokkoooiokwwkooiiooitttotttitioioiiiiiokooiokoitoottiookkwwwkwwwhkkhwwwhhwkwkoookkwwhkkkkhwhkkowwokkhhkhhhkkkokkhhkhwkoooiiooiittititittotitiitioookoioioiiiitioittommmmootitottottoommmoiiommottiiiooititttottooomottiookoookwhkhwkoiiiiokwkkkwkkkoo...
output:
662 qotwtqoqhwotqwkhitwkqtqhomwkhikotithimwkwtikmtwtkmimhmoqikiwktithmhqwkomtiwqtihtwiqmiowhiwoqkqwiqhiqtoihwomhwokwkmthwqmtokwqtmqowkihiomotiokwhkowiktioqwtowokotomwiohmqhkqohqmtqktkioqmkoitkqhkmtqkmkiwtwktkwmhtihkomkhtwotwqkoqkhohwkoqkmtikowhohmtmiktowtkhqtohmqmowqmtmiwtqmkqtqwkitiokqtwmwitmthkhqh...
result:
ok correct answer
Test #30:
score: 0
Accepted
time: 10ms
memory: 10708kb
input:
500000 idiiddvddiidvjhhuuhyyhyhhyyhuuhuhuuhhuhuuuhyhyywwyyhhuhhyyyhhyywxwxwuwuwwuduuduwuwxwyhuhuuhuhhuuhyhywxwuuduwxwuwwwxwuudduuwwxxxwyhuuhyhuhyhhywwxxwxwuwxwuwxwywyyywywwywyhhuuhuhuuhuhyhyyywwxwwywwxwwxwuudduwudduuwuuddduuwuwxwwyhuuuhjjvddvjvvjvdidiyxyyyiidvjhjjjvjvdiiyyiyyxxxukuuuxuuuukhkssijijis...
output:
954 whksuyckywiykdujykxdxsyiwuxuydcdycxzhxiuydzuhcxuyhyusdkyiskhkdxkyhkuvhwixwhkskyxhwxicscvwkhvujisvyvxyudxvuzkjsudwvxwzhzuchsuwdikuswvhuxywkzkcvjsdhjhsuxvwukckwusjyhvjywiyvscxcdwdvjyiwuvxhyhvscidizvjskivkcwskhyhkxhjsvxvjixzdcvuvyswzhjyvhskwivcwdwishxdzuxizivwhjvxwjuizwvzkcxdijhvjhvuykdcyukhvzwkxjc...
result:
ok correct answer
Test #31:
score: 0
Accepted
time: 10ms
memory: 10836kb
input:
500000 qppprppqzzqprorrrroorppqqzzzzqprpqzqqqzqzqpqpqpprpprprpproorororrsspopopsrrsrrspolopppsspolopspsrspsrssssrsspooppsrspoppppsspsppsspolqqmqqllopollqqlloppspoopspopspsppolqlolqqmmmmqlqmmggmqlopssrsssrrspppoollllqqlqmmmmmmmmmgmmmmgmggzosfsosfsosfnznzznzzppppppznfnznfsfsozzgzzzosooozzgmqlqmmqlqllq...
output:
635 nwjbqoslopwfvjlqdvfpognpylrmxbnexyderepnxczjclvxjovlclvpydfworbnxzenvdpylmoxzdcrqxzjfdsnsblpmqldwpsecxldzpvywzsrmgjsjlysnrxycpwygmrsgwqywsqvdgjzgygwqnpdejqbfsbnmswdpyqylvmdsczgzyroefszbsndfczejnwmqxomxvcnbqbzpmcpznfsozgmqlopsrorpqzfxnxjsvwmyvzjgsnlqbobpfcjolsmvecxlgmyqjwlrcoeqobvndrgoxmxcpeclrvf...
result:
ok correct answer
Test #32:
score: 0
Accepted
time: 7ms
memory: 14676kb
input:
500000 yycccyooyycyoyyopipooopoyoycvvcyyoopidddyynyddydyynrroommmmmmorroommmornnnrnyddiddyynrrrnnynnnnyyddynnrnnrrnrornyydidydiiididyydipoyooyyooyyoooppoppoyyycyyycyopipoyyccccyooppiidyynyyydipopidyddididdynrnnnyyyydynrnnnrnnynnnnrrrrrroommororrommorrnnyydydiidddydidydiiippiddynnnnrornrnnnrnroommmmz...
output:
935 wvajkalhplzcdjqtirjgtgxdzljiwobwtvfhaydthieferwrevtwkaixmvarwcztxbkblbfjonqyuxayrqohzlcgdskbmxfglbdihtfilfjuoiwzwpalqaohdjzeylraomvbltplrmlsxpjoihjftiqpvxctuevyxmockodbsuvzmornydipoycvapudywznhsiftdjaogiqgjgqtlbnaikmuanagdwrxjynagvgyrumucuqiqubfysjtbaobwjzfspxnsdliygqxfvfjedkvgkvwzgvxybhfglzezda...
result:
ok correct answer
Test #33:
score: 0
Accepted
time: 11ms
memory: 14628kb
input:
500000 zzaazzaaaaaazaaxazzzaxxxaaxxssswsssssxaxaxxaxsssxxxaaaaxxaazaaxxssxaxxswuueuuwswsxswwuerpqiqpppreeereeerprereeeueerpqpppppqqqppppqqprerreeuwswuwueeeeerrpqpqiiqqppppqqiiqpqprprrrreeeeueuerrprerrprrrppppreerrerpprprreuwwuueuwuwwueuerrpqiwwwwwzxzzzwzwiqqiqqpqqqqiiqiwiwzzxzxzzzxiibbbiixiibiaiiaib...
output:
1180 jrivqxmlmhvwjzetlcufdhkpthcgqhgqktwjfndmxyportwzdgpkteagcvrvxsawpdmnpzapyuyzkzwitspsqpstpuntmscxnqwzvepmoqiodginfqspkvyakuwzgrpxawduwacdozrkrsjvcuvjuzuqfghdbhaojulqxzugfkqcqvgnwbahwaebvkjdsrofyaiqrlelaiyvkvcnzluyfawjwinzgwfilaibixzwiqpreuwsxazhfxkqzsitwzdxfspnpfdqzgvcldjrhladngnsizuewosqjybzpdw...
result:
ok correct answer
Test #34:
score: 0
Accepted
time: 8ms
memory: 14548kb
input:
500000 nhnhihiuuuiuuvvvpupvuuuuuuuuuuuuuuuvvuvvppvpuiupvvvuuvvpuupvppuuicxycyyxyccjjbggwgwwwgbjbjbbgbgwgggghclcccccclevebevellchchchchghhhghggwgwggwwgwgbjbjcjcccyxxccxyyyyxciiiuupuiuicxyxyyccccjbbjjcyyccccyyccjbjjccycjbbgwgbjbgwwghhgggghgwwgbbjjcyxcxxyccccccjbgwwwgwgggwggbjcjjjjbbbggbbjjbgbggbbbggbg...
output:
963 nmtfuqmgsewqaqsptugjnykqlikfhkmtucfwfzpdoidwulkisocxqwuohbvpdxkajgcdtqpdjbuickqxdxcizbopalydkhqmpfywrmxvzjtdvmajiglphgltvjkoqnxwaudtgxbwhncpfuvbalfwclmqlbtireqxvhblzkxdrjzqfvmilqymcpfjxyuizkdmqeoifmsyhqmbysmybsqgnrmtxcugvikatxycqrxveqbahzcjryfykipizbvkehsiacqowulhpzwiagaherksfxygbiljqltlnwdfqipg...
result:
ok correct answer
Test #35:
score: 0
Accepted
time: 8ms
memory: 14672kb
input:
500000 qsssrsyyqaaasaqqasmiqiqqnnnunqnnqnuuueeeueueyyeueunnunnqqimsaaqyqysrrrrrsrrsssyqyssssssyqaqqyqyysrsyssrrssrrrsysrsrsqddddqqssrsrssyqqaqqqyqyqyqyqyqqyyqasaqyssrsssqdqqddlldlldldqsqqdlddqsqsqqdqsqdlllllttuuutttllltlllldqdqddqqqdldltldqssrrssrrrsrrsqqsrrrsqsrsrrssrrsrrrssrsyqaaaqyssrsrrsysyqyyss...
output:
1014 jyhmqorsxgzdvigfygxodpvihnstfpwzsqetmzspstqhbmjcpdqstatuamizbjyanmrpebtcbpdciyetoaqfhcgkzutlnyhwfcraebrahrgsenokptmbjmcdcznjqfbmyayvdtsplbfnujepdrwebzocpdnezqfcwonlciarnboxjxhszuztbentxnytrlrzjgwkcmxrocaptlnqhnqavdpxkdicflbtszkdlxyluldckwbuqniluqwiexlwcxewhdkxsurarzwrpqyqwhvswdxcyqlqnkwpiutqfrl...
result:
ok correct answer
Test #36:
score: 0
Accepted
time: 83ms
memory: 66924kb
input:
500000 abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabaiabacabadabacabaeabacabadabacabafabaca...
output:
131073 sabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabaiabacabadabacabaeabacabadabacabafabac...
result:
ok correct answer
Test #37:
score: 0
Accepted
time: 93ms
memory: 110884kb
input:
499994 bnwhptphwnbbnblgrglbnbbnwhptphwnbiiqnytynqiibnwhptphwnbbnblgrglbnbbnwhptphwnbxdxsipisxdxbnwhptphwnbbnblgrglbnbbnwhptphwnbiiqnytynqiibnwhptphwnbbnblgrglbnbbnwhptphwnbxrrokokorrxbnwhptphwnbbnblgrglbnbbnwhptphwnbiiqnytynqiibnwhptphwnbbnblgrglbnbbnwhptphwnbxdxsipisxdxbnwhptphwnbbnblgrglbnbbnwhptp...
output:
148945 uawjvlbnwhptphwnblgrglbnwhptphwnbiqnytynqibnwhptphwnblgrglbnwhptphwnbxdxsipisxdxbnwhptphwnblgrglbnwhptphwnbiqnytynqibnwhptphwnblgrglbnwhptphwnbxrokorxbnwhptphwnblgrglbnwhptphwnbiqnytynqibnwhptphwnblgrglbnwhptphwnbxdxsipisxdxbnwhptphwnblgrglbnwhptphwnbiqnytynqibnwhptphwnblgrglbnwhptphwnbowxvtv...
result:
ok correct answer
Test #38:
score: 0
Accepted
time: 79ms
memory: 115244kb
input:
499966 slpbptbbxpconvuzxouawxlnycbolulobcynlxwauoxzuvnocpxbbtpbplsjwbgozcqswbptnubhcqsuypptyyghlhgyytppyusqchbuntpbwsqczogbwjslpbptbbxpconvuzxouawxlnycbolulobcynlxwauoxzuvnocpxbbtpbplsswiicydfgggskhwseyixkjksmksgcfcgskmskjkxiyeswhksgggfdyciiwsslpbptbbxpconvuzxouawxlnycbolulobcynlxwauoxzuvnocpxbbtpbp...
output:
225826 buxdmktscrqewpcuclfqoarlxnsoslpbptbxpconvuzxouawxlnycbolulobcynlxwauoxzuvnocpxbtpbplsjwbgozcqswbptnubhcqsuyptyghlhgytpyusqchbuntpbwsqczogbwjslpbptbxpconvuzxouawxlnycbolulobcynlxwauoxzuvnocpxbtpbplswicydfgskhwseyixkjksmksgcfcgskmskjkxiyeswhksgfdyciwslpbptbxpconvuzxouawxlnycbolulobcynlxwauoxzuv...
result:
ok correct answer
Test #39:
score: 0
Accepted
time: 73ms
memory: 117212kb
input:
499759 xojrxdzdgnigulkpwawekhpsgztfyjnsuxnbrnoozojbcmcrcpsgeflynplagrefjzmmqkkiesoutnnpwgwxdslvaevwmnibjwyjeaklivghhtzabneqmmpahuurusmtukvbvnihsqrfzzgrfzagmhavjuoqehczodzarcncnodrjrkoejedrasumjtzomjautnfohtbngbyxzrxdyozljdcniiskmvsgmwieiftfqymdqgcicgqdmyqftfieiwmgsvmksiincdjlzoydxrzxybgnbthofntuajmo...
output:
235344 kedhezahnvmoxvtmqxozqeydsfbcetixgcjtginkfexozturztnwasbulphudxfbgekpupfplrqejteyvnczuvexutgbwbqcpfqwidixpnjltqtcbaskhrtojioymqremhrgewtvgwpyferdlmuejqyhrvogxrugncvfjrtgxjunbkgxergpdfrqhowzdzebeuiodxgckmitraivesgaxvdkeocrsrwlynmslavgrxojrxdzdgnigulkpwawekhpsgztfyjnsuxnbrnozojbcmcrcpsgeflynplag...
result:
ok correct answer
Test #40:
score: 0
Accepted
time: 2ms
memory: 5212kb
input:
262144 abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbab...
output:
2 ba
result:
ok correct answer
Test #41:
score: 0
Accepted
time: 3ms
memory: 5724kb
input:
317811 bababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbab...
output:
2 ab
result:
ok correct answer
Test #42:
score: 0
Accepted
time: 11ms
memory: 37880kb
input:
489114 avvdghamrwfrarnewzadzeoharsueuasmouoammyjsanlkwkalsfpkammouzasnhtvawvqmxaoyvvnaquoetaoqmziamwpdmantenoatwtktaxqfjgavvxsqattpknaexlljapospmakreqwanxyduajypxzakgsueathttpauljvzaedslnahdnuyawjumvankwpzamnlpiauxvdgajkosyahmnlzaxztumaomoseaozmyuaulwemamvndeaglhjiajejtdaftmkialyeogarmqmoangjvlavoss...
output:
107271 avdghamrwfrarnewzadzeoharsueuasmouoamyjsanlkwkalsfpkamouzasnhtvawvqmxaoyvnaquoetaoqmziamwpdmantenoatwtktaxqfjgavxsqatpknaexljapospmakreqwanxyduajypxzakgsueathtpauljvzaedslnahdnuyawjumvankwpzamnlpiauxvdgajkosyahmnlzaxztumaomoseaozmyuaulwemamvndeaglhjiajejtdaftmkialyeogarmqmoangjvlavosfaiqsjkai...
result:
ok correct answer
Test #43:
score: 0
Accepted
time: 11ms
memory: 37916kb
input:
497662 ayjuldafkskdamqeekavumguapgieeaphtnkarimexafsztrapompfauloklazdyfjaehhjyaepsxjaevzwpakepxnayjuqxalnldeaufktdaeringariruyafosddaxggpyakwsyzaqvjdeazwmioaohfzvanjxframrwwjayulovavzwlhamqlepaeikutakovyfazqinkapvoftazmzjlalpkzxahxyqjairwhgarwgfyazntsearkzyqaqfufxalgjumaperkvagvpxiamnqllakhtysauddo...
output:
1673 ayjuldafkskdamqekavumguapgieaphtnkarimexafsztrapompfauloklazdyfjaehjyaepsxjaevzwpakepxnayjuqxalnldeaufktdaeringariruyafosdaxgpyakwsyzaqvjdeazwmioaohfzvanjxframrwjayulovavzwlhamqlepaeikutakovyfazqinkapvoftazmzjlalpkzxahxyqjairwhgarwgfyazntsearkzyqaqfufxalgjumaperkvagvpxiamnqlakhtysaudodapkryapdf...
result:
ok correct answer
Extra Test:
score: 0
Extra Test Passed