QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#713006#9586. 野兽节拍xydCatGirl#AC ✓55ms25720kbC++202.1kb2024-11-05 17:46:212024-11-05 17:46:21

Judging History

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

  • [2024-11-05 17:46:21]
  • 评测
  • 测评结果:AC
  • 用时:55ms
  • 内存:25720kb
  • [2024-11-05 17:46:21]
  • 提交

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