QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#750043 | #9586. 野兽节拍 | propane | AC ✓ | 76ms | 28168kb | C++20 | 2.0kb | 2024-11-15 12:20:01 | 2024-11-15 12:20:02 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<queue>
using namespace std;
using LL = long long;
int a[1000005], l[1000005], r[1000005];
int v[1000005];
vector<int> s[26 * 26 * 26];
int target[3];
vector<int> del;
int ts;
int check(int x){
if (v[x] == ts) return 0;
if (r[x] == 0 or r[r[x]] == 0) return 0;
if (a[x] != target[0] or a[r[x]] != target[1] or a[r[r[x]]] != target[2]) return 0;
v[x] = v[r[x]] = v[r[r[x]]] = ts;
int pre = l[x];
int nxt = r[r[r[x]]];
if (pre != 0){
r[pre] = nxt;
del.push_back(pre);
}
if (nxt != 0){
del.push_back(nxt);
l[nxt] = pre;
}
int ans = 1;
if (l[x] != 0 and l[l[x]] != 0){
int t = check(l[l[x]]);
ans += t;
if (t > 0) return ans;
}
if (l[x] != 0){
ans += check(l[x]);
}
return ans;
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
string str;
cin >> str;
for(int i = 1; i <= n; i++){
a[i] = str[i - 1] - 'a';
l[i] = i - 1;
r[i] = i + 1;
}
pair<int, int> ans{0, 0};
for(int i = 1; i + 2 <= n; i++){
int t = a[i] * 26 * 26 + a[i + 1] * 26 + a[i + 2];
s[t].push_back(i);
}
r[n] = 0;
for(int i = 0; i < 26 * 26 * 26; i++){
if (s[i].empty()) continue;
target[0] = i / (26 * 26);
target[1] = i % (26 * 26) / 26;
target[2] = i % 26;
++ts;
int sum = 0;
for(auto x : s[i]){
sum += check(x);
}
ans = max(ans, pair(sum, -i));
for(auto x : del){
l[x] = x - 1;
r[x] = x + 1;
}
del.clear();
}
cout << ans.first << '\n';
int t = -ans.second;
cout << char('a' + t / (26 * 26)) << char('a' + t % (26 * 26) / 26) << char('a' + t % 26) << '\n';
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 9700kb
input:
10 aaababbaab
output:
3 aab
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 9832kb
input:
14 liaoningdalian
output:
2 lia
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 9764kb
input:
3 zyl
output:
1 zyl
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 24ms
memory: 24340kb
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabababababababababababababababababaaaaaaaaaaaaaaaaaacacacacacacacacacacacacacacacacacaaaaaaaaaaaaaaaaaadadadadadadadadadadadadadadadadadaaaaaaaaaaaaaaaaaaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaaaaaaaaaaaaaaaaaafafafafafafafafafafa...
output:
3717 aaa
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 20ms
memory: 25288kb
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaababaaaaaaabababababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaacacacacaaaaacacacacacacacaaacaaaaaaaaaaaaaaaaaadadaaaaaaaaadaaadadaaaaadaaaaadadaaaaaaaaaaaaaaaaaaaaaaeaeaaaaaeaaaaaaaeaeaeaaaaaaaeaaaaaaaaaaaaaaaaaaaafaaaaaaafafafafafa...
output:
7571 xxx
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 34ms
memory: 24704kb
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaababaaaaaaaaabaaabaaaaaaaaababaaaaaaaaaaaaaaaaaaaaaaaaaacaaaaacaaaaaaaaacacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaadaaaaadaaaaaaaaaaaaaaaaaaaaeaeaeaaaaaeaaaaaeaaaaaeaeaaaeaeaaaaaaaaaaaaaaaaaafafaaafafaaaaaaaaaaa...
output:
6680 xxx
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 42ms
memory: 23968kb
input:
667888 eqjszvsxnlvgskosbdoyavaooutvfysniyfplykvmcnsgaomyeqqokqsrdykzfbzsbtkvotfsmmjgkhjhhxbgntmdzmxmexstdwwjrtsmumrrcvkeoluhcpvazdnoxscqibnyytrryywasediqzfsptsxggweogoxeoxhtxaynefaoscgobuxcprquxqzhircomstyufqkfdykbbuibknkjeyebhssdtqbxsdbqiwgseiaezqldbswtpdziicnnwvmxcozqttffglgefiwzdkbfnqmiuicjdcdodx...
output:
63 uzb
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 2ms
memory: 10032kb
input:
1000 baddacbabcddacdcbacaccbadddbadbdaddcdabbbcccdaaaddbadcdbddccadbbddcccaaadacdcbcbbccccabdbcbcdadacadcbcdbdbcddccddbbabdcabdabadddbbdacabdbbdddddaacdabdddddddbddbdcbadbcaaddccdbcbddaccdacbdaabbabababdcabdadddbacabcdbcddcdacaaddddbaccbbcbaacbcdcbbcdaacbaddcbcbcadaabacadadbaaababbccaddaccddbccdcbca...
output:
26 ddc
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 2ms
memory: 9724kb
input:
1000 ddcddcbbbcabbbbbccbaaddcbaaddcabbabbabdaacdcdbacbddabccddcadcaccadbaddcbcdccbddabccadadcdddbaaacdacadadddadacccbbddcacccccaccacccadbbacacbdccdbccdaabdabdabbddacdccdbaacdddcdbadabddbddbddbabcccdccbcddcdbbbcaaacbcdcdbdccabbdbcbadbbbbacddccadbbaddacaddcdbbbdcdbcbbdaaacadbccbabbbaacbcbaababbbabcdac...
output:
27 ddc
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 2ms
memory: 9808kb
input:
1000 bbccbcaaccbcdccaacbbcbadbabadddaabacadadacbbdacabdbdcaaaddabbabcacbddcdaccbcbcbddcabbbadacaaabcacbaabaccaccbdbbcddbddcadbbabaadcdccbbaacdbaddacaccbbabdacdbbbddccbcdbaccbbcddbbbddaaadccacdddddccbbbdcdadabbbcccbbbdddacbabacdccbdcdbdaacdabaaaccbbccdcddcdcdbcacacccdbabcaaadabbddcdbdbaacaaddcbcbbccb...
output:
24 bab
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 7ms
memory: 26400kb
input:
931528 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
310509 aaa
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 9ms
memory: 24680kb
input:
615161 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205053 aaa
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 7ms
memory: 25296kb
input:
623944 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
200880 aaa
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 43ms
memory: 26728kb
input:
1000000 baabaabbaaaabbababbbabbbabaabbbaaaabaabbababbbbaabbaabbabbbbbbbaaaaabbbbbababaaababbbaababbbbbbaababbbaaabbbbbbbbababbbbabbbbabbbbbbbaabaaabbaaaaaaaaabbabababbabbbbaabbbbbaaabbbbabbbbaababbabaaaaaababbbaabbabbbbaaaabbbbaabbababaababbababbbbaaaabbbbabbaaabbbbaabaaaabbbbbaababaaabbbabaabababba...
output:
191420 aab
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 37ms
memory: 26660kb
input:
1000000 aabbbbbcbacccabaaaccccaacaccccbcaabacaaabacccabbcaccaaacbaabcbacbcaaababacbbacaabcbaaacbbaaaaaabbaaabbcbaabaccaacccacbbaabbaaaaaabbaccbcaabcabcacabcaacbacaccbbcbbbccbbbcaacbaabcacacccbcbacaccaaaccabaaccbbcbbbcbcabbcbabbabacbbbcbbbcacbcabbaaacbaaaccbacacabcccbbabaccaccbcbbccacbbabbbacacabaccc...
output:
40521 ccb
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 59ms
memory: 24736kb
input:
1000000 acdbcbcccdddcccdccadbdcccaaacbbdadbdacacaadcadadccdbbacdbcbddadabbdcbccbcadadbaddabdbadbbdcbcdcabbdabadabaaaddbcdbbaddcaadbcbcdacdbaacdbddbdacaaacadbbcadadacdbdcdcdccddbdddccacacbbcbbccacbdbbbdbcddbdcaccdcdcdbababbdbcbcacddddaadadcdcbbacbbdbddaadbbbbcccccabbadddbbbaaaddccdaadcaddbbdcdcdaabaa...
output:
16769 abd
result:
ok 2 lines
Test #17:
score: 0
Accepted
time: 65ms
memory: 24716kb
input:
1000000 abbaccdaecaaeadcaabecddbdedbcbebeeaeabaaaacedcaaabbbcabcbddcdcececcceacacaedeebaddabcdedeadbacabbbaadbeeeebbdaeadcacadadddbdbcaeeeaeddaccdceacebbaabccacdbdacdbcabaeeddeccecdcaeedbadbceebbcddbbeeecdeceabbdccccadcbeedacadceabadabcbcbbecddacbcbbbbbbadbacbdbcdbecadeecbeabceccabccdecccdbdcdbbeeee...
output:
8338 dce
result:
ok 2 lines
Test #18:
score: 0
Accepted
time: 28ms
memory: 26388kb
input:
1000000 abbbbbbabbababbbbaabababbbaaaaabbabbaaabababaaaababbbaaaabaababaaababbbaabbbbbbbaaaaabaabbabaabaaabaababaaabbabaaaaabbbbaabaababbbbbbbabaabaaabbabbbaaababaababababbbaababbaabbbbbaaabbaabbbbabbaabaababbaabbbabaaaabbababaabbabbabbabaabbbbaaababbbbbaaaabaaabbaabaaabaabbaabaaabaabaabbbaaaaabbbab...
output:
191383 bba
result:
ok 2 lines
Test #19:
score: 0
Accepted
time: 38ms
memory: 26304kb
input:
1000000 aabbcbcaabbabccabbbccabbcbacabccccccbbbcbccbabacacaccccbcbcbacaaaababbbabacacbbccaacbaacbacccabbabbbccbcbbbcbbacacaccbbaacbaaabaabbaccacccbcbbcacbbacabaabbabcacccaccbcacccccccbcbacaabbcbaaabaaabcabbaacabaaaaaccbabaabccbaabacbbcbbaabcbccccbcaccbbbccbbbbaabacbacbbaacbcccccbabacacbcccaaaccccaca...
output:
40925 caa
result:
ok 2 lines
Test #20:
score: 0
Accepted
time: 7ms
memory: 28168kb
input:
1000000 babbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabb...
output:
333333 abb
result:
ok 2 lines
Test #21:
score: 0
Accepted
time: 31ms
memory: 26260kb
input:
999986 abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefg...
output:
38461 abc
result:
ok 2 lines
Test #22:
score: 0
Accepted
time: 2ms
memory: 10328kb
input:
5388 xxyzyzaaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwabcabdabeabfabgabhabiabjabkablabmabnaboabpabqabrabsabtabuabvabwacdaceacfacgachaciacjackaclacmacnacoacpacqacracsactacuacvacwadeadfadgadhadiadjadkadladmadnadoadpadqadradsadtaduadvadwaefaegaehaeiaejaekaelaemaenaeoaepaeqaera...
output:
2 xyz
result:
ok 2 lines
Test #23:
score: 0
Accepted
time: 31ms
memory: 25248kb
input:
1000000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaafaaf...
output:
87 fwu
result:
ok 2 lines
Test #24:
score: 0
Accepted
time: 0ms
memory: 9764kb
input:
6 ababaa
output:
1 aba
result:
ok 2 lines
Test #25:
score: 0
Accepted
time: 2ms
memory: 9712kb
input:
6 aababa
output:
2 aba
result:
ok 2 lines
Test #26:
score: 0
Accepted
time: 64ms
memory: 26532kb
input:
1000000 zenudggmyopddhszhrbmftgzmjorabhgojdtfnzxjkayjlkgczsyshczutkdchiytqlfsevymipufxkxojlvkkqxvjhpjmcxeiluubblcdiwjphlpzwvknsyvbcodpyktizgatrlieiikktghixbikehsiknjuateltwkyyhgabygwtclyeyquaoiqnypoxnvyzvyhfejoljxnwhkkcgitdebuutnzzvawollaiesjsnlbdvdarlewlnusmgwhulzimadkzlngoukodeljdpjpxxdljooczhewfz...
output:
90 cze
result:
ok 2 lines
Test #27:
score: 0
Accepted
time: 59ms
memory: 26484kb
input:
1000000 rtzxovxqfapkdmelxiyjroohufhbakpmmvaxqcptiwtcijcabvobzwbrespqhpvjidgmlvjetwieqngdfbinbsjyfgxofbunxgmhjnkdhhwzjaqqhxjurewcpktfzgxdheuuyfrcmqxykcxjaeotsutxkedqsoyoxzvcspgbnzrwypgdqnfbxywblqvdufggbbskburngiyxtrauvhxjeposnzhcbxlkcczhvpxdbmegacemorezpcsnlzbbiasssvhgneavpnoeikfrhkxeredmmsuowksdtoon...
output:
88 yqs
result:
ok 2 lines
Test #28:
score: 0
Accepted
time: 76ms
memory: 26384kb
input:
1000000 ljmybiqxmnqqbsoxkyvgdiupdyamxtyvhjvbdsgogfkgghvubrlefmxiorufmakswraubnxjakandedlvsfepzcxnelmzqkeqbqrawwukmicllbvauvtzuajjsmxuuuzvypgzstvpbmpktcluzglzelpaayvyhwkqmzixfotvxjsohrctbgdezsorqehyxozheoxcgcwcellqwdhgdqjxkyiaetlntxbfgkehdlfkoococgfziqkcibndisxwwsanicoxybhrtpphfibclqqbtmaxbendpnagfxb...
output:
87 qfh
result:
ok 2 lines
Test #29:
score: 0
Accepted
time: 63ms
memory: 26452kb
input:
1000000 fyyymvhdtbqyaxbiypqdqdaykusyvdgccwsfohwjgrckffnqanhhkaubwqzsrjzcleuatejofztxpvaqmidwghvywbbltfcujzrerfgjoowflukcusivimfoedcoqlstisjtzfvmtnbhllflpuyfhoagswuyfbufmzbncwvocvzngafbvnkfkbrcutmldoxqnikmdtodzzzzmchstallsfjwmjhszqiqhmwcrsaftrzvebgwhydynoiotqhqkrqhgxxufscrvapaebmmxljfiiuoiiomnxhwwxgp...
output:
92 nsk
result:
ok 2 lines
Test #30:
score: 0
Accepted
time: 49ms
memory: 26388kb
input:
1000000 zokbxiahaosfyclumgnaczggrnljumplxknibxmeedvnefhkygdkqosshpegwunnzsohmxxumnnhckwyczaowpoxezqlovukcuuqgrsbrtifngthlquuqdjvyltgjbrmwoefypvdyzqwlainjoqxrzrwktnblvszfndrjodikurlytsayblhpdnrytxnhfejtjfzeeamttmnjgkffwelozvmyosbmoufjpjzbeohbulotcinspqmyurolxwlwloobkszpnddxhrkbxoytmdsqxaetqzmufcslqpd...
output:
89 ynq
result:
ok 2 lines
Extra Test:
score: 0
Extra Test Passed