QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#713006 | #9586. 野兽节拍 | xydCatGirl# | AC ✓ | 55ms | 25720kb | C++20 | 2.1kb | 2024-11-05 17:46:21 | 2024-11-05 17:46:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n;
string s, t;
int f(char a, char b, char c) {
return (a - 'a') * 26 * 26 + (b - 'a') * 26 + (c - 'a');
}
const int N = 26 * 26 * 26, M = 1e6 + 5;
vector<int> pos[N];
int nex[M], pre[M];
int main() {
cin >> n >> s; s = " " + s; t.resize(3);
for (int i = 1; i <= n - 2; i++) pos[f(s[i], s[i + 1], s[i + 2])].push_back(i);
int ans1 = -1, ans2 = 0;
for (int i = 0; i <= n; i++) nex[i] = i + 1;
nex[n + 1] = n + 1;
for (int i = 1; i <= n + 1; i++) pre[i] = i - 1;
for (int i = 0; i < N; i++) {
if (pos[i].size()) {
t[2] = 'a' + (i % 26);
t[1] = 'a' + ((i / 26) % 26);
t[0] = 'a' + ((i / 26 / 26) % 26);
vector<int> del;
int cnt = 0, now = pos[i][0];
auto check = [&](int x) -> bool {
if (!x) return 0;
int y = nex[x], z = nex[y];
if (y == n + 1 || z == n + 1) return 0;
if (s[x] == t[0] && s[y] == t[1] && s[z] == t[2]) return 1;
return 0;
} ;
int cur = 0, len = pos[i].size();
while (1) {
cnt ++;
int now2 = nex[now], now3 = nex[now2], nex4 = nex[now3];
del.push_back(now); del.push_back(now2); del.push_back(now3);
int pre1 = pre[now], pre2 = pre[pre1];
nex[pre1] = nex[now3]; pre[nex[now3]] = pre1;
if (check(pre2)) now = pre2;
else if (check(pre1)) now = pre1;
else {
while (cur < len && pos[i][cur] < nex4) cur ++;
if (cur < len) now = pos[i][cur];
else break;
}
}
if (cnt > ans1) {
ans1 = cnt; ans2 = i;
}
for (int v : del) pre[v] = v - 1, nex[v] = v + 1, nex[v - 1] = v, pre[v + 1] = v;
}
}
cout << ans1 << '\n';
int i = ans2;
t[2] = 'a' + (i % 26);
t[1] = 'a' + ((i / 26) % 26);
t[0] = 'a' + ((i / 26 / 26) % 26);
cout << t;
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5640kb
input:
10 aaababbaab
output:
3 aab
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5832kb
input:
14 liaoningdalian
output:
2 lia
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 5652kb
input:
3 zyl
output:
1 zyl
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 29ms
memory: 16756kb
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabababababababababababababababababaaaaaaaaaaaaaaaaaacacacacacacacacacacacacacacacacacaaaaaaaaaaaaaaaaaadadadadadadadadadadadadadadadadadaaaaaaaaaaaaaaaaaaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaaaaaaaaaaaaaaaaaafafafafafafafafafafa...
output:
3717 aaa
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 35ms
memory: 17456kb
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaababaaaaaaabababababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaacacacacaaaaacacacacacacacaaacaaaaaaaaaaaaaaaaaadadaaaaaaaaadaaadadaaaaadaaaaadadaaaaaaaaaaaaaaaaaaaaaaeaeaaaaaeaaaaaaaeaeaeaaaaaaaeaaaaaaaaaaaaaaaaaaaafaaaaaaafafafafafa...
output:
7571 xxx
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 38ms
memory: 16936kb
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaababaaaaaaaaabaaabaaaaaaaaababaaaaaaaaaaaaaaaaaaaaaaaaaacaaaaacaaaaaaaaacacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaadaaaaadaaaaaaaaaaaaaaaaaaaaeaeaeaaaaaeaaaaaeaaaaaeaeaaaeaeaaaaaaaaaaaaaaaaaafafaaafafaaaaaaaaaaa...
output:
6680 xxx
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 31ms
memory: 16828kb
input:
667888 eqjszvsxnlvgskosbdoyavaooutvfysniyfplykvmcnsgaomyeqqokqsrdykzfbzsbtkvotfsmmjgkhjhhxbgntmdzmxmexstdwwjrtsmumrrcvkeoluhcpvazdnoxscqibnyytrryywasediqzfsptsxggweogoxeoxhtxaynefaoscgobuxcprquxqzhircomstyufqkfdykbbuibknkjeyebhssdtqbxsdbqiwgseiaezqldbswtpdziicnnwvmxcozqttffglgefiwzdkbfnqmiuicjdcdodx...
output:
63 uzb
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 5636kb
input:
1000 baddacbabcddacdcbacaccbadddbadbdaddcdabbbcccdaaaddbadcdbddccadbbddcccaaadacdcbcbbccccabdbcbcdadacadcbcdbdbcddccddbbabdcabdabadddbbdacabdbbdddddaacdabdddddddbddbdcbadbcaaddccdbcbddaccdacbdaabbabababdcabdadddbacabcdbcddcdacaaddddbaccbbcbaacbcdcbbcdaacbaddcbcbcadaabacadadbaaababbccaddaccddbccdcbca...
output:
26 ddc
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 1ms
memory: 5660kb
input:
1000 ddcddcbbbcabbbbbccbaaddcbaaddcabbabbabdaacdcdbacbddabccddcadcaccadbaddcbcdccbddabccadadcdddbaaacdacadadddadacccbbddcacccccaccacccadbbacacbdccdbccdaabdabdabbddacdccdbaacdddcdbadabddbddbddbabcccdccbcddcdbbbcaaacbcdcdbdccabbdbcbadbbbbacddccadbbaddacaddcdbbbdcdbcbbdaaacadbccbabbbaacbcbaababbbabcdac...
output:
27 ddc
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 1ms
memory: 5824kb
input:
1000 bbccbcaaccbcdccaacbbcbadbabadddaabacadadacbbdacabdbdcaaaddabbabcacbddcdaccbcbcbddcabbbadacaaabcacbaabaccaccbdbbcddbddcadbbabaadcdccbbaacdbaddacaccbbabdacdbbbddccbcdbaccbbcddbbbddaaadccacdddddccbbbdcdadabbbcccbbbdddacbabacdccbdcdbdaacdabaaaccbbccdcddcdcdbcacacccdbabcaaadabbddcdbdbaacaaddcbcbbccb...
output:
24 bab
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 11ms
memory: 22324kb
input:
931528 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
310509 aaa
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 8ms
memory: 19944kb
input:
615161 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205053 aaa
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 13ms
memory: 22340kb
input:
623944 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
200880 aaa
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 40ms
memory: 24332kb
input:
1000000 baabaabbaaaabbababbbabbbabaabbbaaaabaabbababbbbaabbaabbabbbbbbbaaaaabbbbbababaaababbbaababbbbbbaababbbaaabbbbbbbbababbbbabbbbabbbbbbbaabaaabbaaaaaaaaabbabababbabbbbaabbbbbaaabbbbabbbbaababbabaaaaaababbbaabbabbbbaaaabbbbaabbababaababbababbbbaaaabbbbabbaaabbbbaabaaaabbbbbaababaaabbbabaabababba...
output:
191420 aab
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 42ms
memory: 18940kb
input:
1000000 aabbbbbcbacccabaaaccccaacaccccbcaabacaaabacccabbcaccaaacbaabcbacbcaaababacbbacaabcbaaacbbaaaaaabbaaabbcbaabaccaacccacbbaabbaaaaaabbaccbcaabcabcacabcaacbacaccbbcbbbccbbbcaacbaabcacacccbcbacaccaaaccabaaccbbcbbbcbcabbcbabbabacbbbcbbbcacbcabbaaacbaaaccbacacabcccbbabaccaccbcbbccacbbabbbacacabaccc...
output:
40521 ccb
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 49ms
memory: 17112kb
input:
1000000 acdbcbcccdddcccdccadbdcccaaacbbdadbdacacaadcadadccdbbacdbcbddadabbdcbccbcadadbaddabdbadbbdcbcdcabbdabadabaaaddbcdbbaddcaadbcbcdacdbaacdbddbdacaaacadbbcadadacdbdcdcdccddbdddccacacbbcbbccacbdbbbdbcddbdcaccdcdcdbababbdbcbcacddddaadadcdcbbacbbdbddaadbbbbcccccabbadddbbbaaaddccdaadcaddbbdcdcdaabaa...
output:
16769 abd
result:
ok 2 lines
Test #17:
score: 0
Accepted
time: 52ms
memory: 16920kb
input:
1000000 abbaccdaecaaeadcaabecddbdedbcbebeeaeabaaaacedcaaabbbcabcbddcdcececcceacacaedeebaddabcdedeadbacabbbaadbeeeebbdaeadcacadadddbdbcaeeeaeddaccdceacebbaabccacdbdacdbcabaeeddeccecdcaeedbadbceebbcddbbeeecdeceabbdccccadcbeedacadceabadabcbcbbecddacbcbbbbbbadbacbdbcdbecadeecbeabceccabccdecccdbdcdbbeeee...
output:
8338 dce
result:
ok 2 lines
Test #18:
score: 0
Accepted
time: 44ms
memory: 24184kb
input:
1000000 abbbbbbabbababbbbaabababbbaaaaabbabbaaabababaaaababbbaaaabaababaaababbbaabbbbbbbaaaaabaabbabaabaaabaababaaabbabaaaaabbbbaabaababbbbbbbabaabaaabbabbbaaababaababababbbaababbaabbbbbaaabbaabbbbabbaabaababbaabbbabaaaabbababaabbabbabbabaabbbbaaababbbbbaaaabaaabbaabaaabaabbaabaaabaabaabbbaaaaabbbab...
output:
191383 bba
result:
ok 2 lines
Test #19:
score: 0
Accepted
time: 36ms
memory: 18720kb
input:
1000000 aabbcbcaabbabccabbbccabbcbacabccccccbbbcbccbabacacaccccbcbcbacaaaababbbabacacbbccaacbaacbacccabbabbbccbcbbbcbbacacaccbbaacbaaabaabbaccacccbcbbcacbbacabaabbabcacccaccbcacccccccbcbacaabbcbaaabaaabcabbaacabaaaaaccbabaabccbaabacbbcbbaabcbccccbcaccbbbccbbbbaabacbacbbaacbcccccbabacacbcccaaaccccaca...
output:
40925 caa
result:
ok 2 lines
Test #20:
score: 0
Accepted
time: 16ms
memory: 25720kb
input:
1000000 babbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabb...
output:
333333 abb
result:
ok 2 lines
Test #21:
score: 0
Accepted
time: 30ms
memory: 18740kb
input:
999986 abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefg...
output:
38461 abc
result:
ok 2 lines
Test #22:
score: 0
Accepted
time: 0ms
memory: 6224kb
input:
5388 xxyzyzaaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwabcabdabeabfabgabhabiabjabkablabmabnaboabpabqabrabsabtabuabvabwacdaceacfacgachaciacjackaclacmacnacoacpacqacracsactacuacvacwadeadfadgadhadiadjadkadladmadnadoadpadqadradsadtaduadvadwaefaegaehaeiaejaekaelaemaenaeoaepaeqaera...
output:
2 xyz
result:
ok 2 lines
Test #23:
score: 0
Accepted
time: 26ms
memory: 17584kb
input:
1000000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaafaaf...
output:
87 fwu
result:
ok 2 lines
Test #24:
score: 0
Accepted
time: 1ms
memory: 5660kb
input:
6 ababaa
output:
1 aba
result:
ok 2 lines
Test #25:
score: 0
Accepted
time: 0ms
memory: 5844kb
input:
6 aababa
output:
2 aba
result:
ok 2 lines
Test #26:
score: 0
Accepted
time: 53ms
memory: 18700kb
input:
1000000 zenudggmyopddhszhrbmftgzmjorabhgojdtfnzxjkayjlkgczsyshczutkdchiytqlfsevymipufxkxojlvkkqxvjhpjmcxeiluubblcdiwjphlpzwvknsyvbcodpyktizgatrlieiikktghixbikehsiknjuateltwkyyhgabygwtclyeyquaoiqnypoxnvyzvyhfejoljxnwhkkcgitdebuutnzzvawollaiesjsnlbdvdarlewlnusmgwhulzimadkzlngoukodeljdpjpxxdljooczhewfz...
output:
90 cze
result:
ok 2 lines
Test #27:
score: 0
Accepted
time: 44ms
memory: 18520kb
input:
1000000 rtzxovxqfapkdmelxiyjroohufhbakpmmvaxqcptiwtcijcabvobzwbrespqhpvjidgmlvjetwieqngdfbinbsjyfgxofbunxgmhjnkdhhwzjaqqhxjurewcpktfzgxdheuuyfrcmqxykcxjaeotsutxkedqsoyoxzvcspgbnzrwypgdqnfbxywblqvdufggbbskburngiyxtrauvhxjeposnzhcbxlkcczhvpxdbmegacemorezpcsnlzbbiasssvhgneavpnoeikfrhkxeredmmsuowksdtoon...
output:
88 yqs
result:
ok 2 lines
Test #28:
score: 0
Accepted
time: 50ms
memory: 18704kb
input:
1000000 ljmybiqxmnqqbsoxkyvgdiupdyamxtyvhjvbdsgogfkgghvubrlefmxiorufmakswraubnxjakandedlvsfepzcxnelmzqkeqbqrawwukmicllbvauvtzuajjsmxuuuzvypgzstvpbmpktcluzglzelpaayvyhwkqmzixfotvxjsohrctbgdezsorqehyxozheoxcgcwcellqwdhgdqjxkyiaetlntxbfgkehdlfkoococgfziqkcibndisxwwsanicoxybhrtpphfibclqqbtmaxbendpnagfxb...
output:
87 qfh
result:
ok 2 lines
Test #29:
score: 0
Accepted
time: 54ms
memory: 18524kb
input:
1000000 fyyymvhdtbqyaxbiypqdqdaykusyvdgccwsfohwjgrckffnqanhhkaubwqzsrjzcleuatejofztxpvaqmidwghvywbbltfcujzrerfgjoowflukcusivimfoedcoqlstisjtzfvmtnbhllflpuyfhoagswuyfbufmzbncwvocvzngafbvnkfkbrcutmldoxqnikmdtodzzzzmchstallsfjwmjhszqiqhmwcrsaftrzvebgwhydynoiotqhqkrqhgxxufscrvapaebmmxljfiiuoiiomnxhwwxgp...
output:
92 nsk
result:
ok 2 lines
Test #30:
score: 0
Accepted
time: 55ms
memory: 18656kb
input:
1000000 zokbxiahaosfyclumgnaczggrnljumplxknibxmeedvnefhkygdkqosshpegwunnzsohmxxumnnhckwyczaowpoxezqlovukcuuqgrsbrtifngthlquuqdjvyltgjbrmwoefypvdyzqwlainjoqxrzrwktnblvszfndrjodikurlytsayblhpdnrytxnhfejtjfzeeamttmnjgkffwelozvmyosbmoufjpjzbeohbulotcinspqmyurolxwlwloobkszpnddxhrkbxoytmdsqxaetqzmufcslqpd...
output:
89 ynq
result:
ok 2 lines
Extra Test:
score: 0
Extra Test Passed