QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#858498#9586. 野兽节拍dark_moonAC ✓108ms97696kbC++142.5kb2025-01-16 17:53:422025-01-16 17:53:43

Judging History

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

  • [2025-01-16 17:53:43]
  • 评测
  • 测评结果:AC
  • 用时:108ms
  • 内存:97696kb
  • [2025-01-16 17:53:42]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
auto IOS = ios::sync_with_stdio(false);
auto CIN = cin.tie(nullptr);
const int N = 1e6 + 5;
int n;
char s[N];
vector<int> v[N];
int nxt[N], la[N];
bool e[N];
int get(int x){
    int ans = 0;
    for(int i = 1; i <= 3; i ++){
        if(x > n){
            return -1;
        }
        ans = ans * 30 + (s[x] - 'a' + 1);
        x = nxt[x];
        // printf("*** %lld\n", x);
    }
    // printf("\n");
    return ans;
}
stack<pair<int, int> > snxt, sla;
stack<int> se;
void build(){
    while(snxt.size()){
        nxt[snxt.top().fi] = snxt.top().se;
        snxt.pop();
    }
    while(sla.size()){
        la[sla.top().fi] = sla.top().se;
        sla.pop();
    }
    while(se.size()){
        e[se.top()] = 0;
        se.pop();
    }
    return;
}
void del(int x){
    snxt.push(mp(la[x], nxt[la[x]]));
    nxt[la[x]] = nxt[x];
    sla.push(mp(nxt[x], la[nxt[x]]));
    la[nxt[x]] = la[x];
    se.push(x);
    e[x] = 1;
    return;
}
signed main(){
    cin >> n >> s + 1;
    nxt[0] = 1;
    la[0] = 0;
    la[n + 1] = n;
    nxt[n + 1] = n + 1;
    for(int i = 1; i <= n; i ++){
        la[i] = i - 1;
        nxt[i] = i + 1;
    }
    for(int i = 1; i <= n - 3 + 1; i ++){
        v[get(i)].push_back(i);
    }
    int ans = 0, p = 0;
    for(int i = 931; i <= 30000; i ++){
        // if(i != 932){
        //     continue;
        // }
        build();
        int sum = 0;
        for(int j : v[i]){
            if(e[j] == 0 && e[j + 1] == 0 && e[j + 2] == 0){
                sum ++;
                int nl = j, nr = j + 2;
                int vl = la[nl];
                del(j);
                del(j + 1);
                del(j + 2);
                // printf("--- %lld %lld\n", vl, nxt[nxt[vl]]);
                while(nxt[nxt[vl]] <= n && nxt[nxt[vl]] >= nr){
                    int vvl = la[vl];
                    if(get(vl) == i){
                        sum ++;
                        del(nxt[vl]);
                        del(nxt[vl]);
                        del(vl);
                    }
                    vl = vvl;
                    if(vl == 0){
                        break;
                    }
                }
            }
        }
        if(sum > ans){
            ans = sum;
            p = i;
        }
    }
    cout << ans << "\n" << (char)('a' + p / 900 - 1) << (char)('a' + p % 900 / 30 - 1) << (char)('a' + p % 30 - 1);
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 33032kb

input:

10
aaababbaab

output:

3
aab

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 30312kb

input:

14
liaoningdalian

output:

2
lia

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 2ms
memory: 30436kb

input:

3
zyl

output:

1
zyl

result:

ok 2 lines

Test #4:

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

input:

896376
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabababababababababababababababababaaaaaaaaaaaaaaaaaacacacacacacacacacacacacacacacacacaaaaaaaaaaaaaaaaaadadadadadadadadadadadadadadadadadaaaaaaaaaaaaaaaaaaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaaaaaaaaaaaaaaaaaafafafafafafafafafafa...

output:

3717
aaa

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 54ms
memory: 54616kb

input:

896376
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaababaaaaaaabababababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaacacacacaaaaacacacacacacacaaacaaaaaaaaaaaaaaaaaadadaaaaaaaaadaaadadaaaaadaaaaadadaaaaaaaaaaaaaaaaaaaaaaeaeaaaaaeaaaaaaaeaeaeaaaaaaaeaaaaaaaaaaaaaaaaaaaafaaaaaaafafafafafa...

output:

7571
xxx

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 59ms
memory: 54124kb

input:

896376
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaababaaaaaaaaabaaabaaaaaaaaababaaaaaaaaaaaaaaaaaaaaaaaaaacaaaaacaaaaaaaaacacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaadaaaaadaaaaaaaaaaaaaaaaaaaaeaeaeaaaaaeaaaaaeaaaaaeaeaaaeaeaaaaaaaaaaaaaaaaaafafaaafafaaaaaaaaaaa...

output:

6680
xxx

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 59ms
memory: 53264kb

input:

667888
eqjszvsxnlvgskosbdoyavaooutvfysniyfplykvmcnsgaomyeqqokqsrdykzfbzsbtkvotfsmmjgkhjhhxbgntmdzmxmexstdwwjrtsmumrrcvkeoluhcpvazdnoxscqibnyytrryywasediqzfsptsxggweogoxeoxhtxaynefaoscgobuxcprquxqzhircomstyufqkfdykbbuibknkjeyebhssdtqbxsdbqiwgseiaezqldbswtpdziicnnwvmxcozqttffglgefiwzdkbfnqmiuicjdcdodx...

output:

63
uzb

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 5ms
memory: 33380kb

input:

1000
baddacbabcddacdcbacaccbadddbadbdaddcdabbbcccdaaaddbadcdbddccadbbddcccaaadacdcbcbbccccabdbcbcdadacadcbcdbdbcddccddbbabdcabdabadddbbdacabdbbdddddaacdabdddddddbddbdcbadbcaaddccdbcbddaccdacbdaabbabababdcabdadddbacabcdbcddcdacaaddddbaccbbcbaacbcdcbbcdaacbaddcbcbcadaabacadadbaaababbccaddaccddbccdcbca...

output:

26
ddc

result:

ok 2 lines

Test #9:

score: 0
Accepted
time: 3ms
memory: 30436kb

input:

1000
ddcddcbbbcabbbbbccbaaddcbaaddcabbabbabdaacdcdbacbddabccddcadcaccadbaddcbcdccbddabccadadcdddbaaacdacadadddadacccbbddcacccccaccacccadbbacacbdccdbccdaabdabdabbddacdccdbaacdddcdbadabddbddbddbabcccdccbcddcdbbbcaaacbcdcdbdccabbdbcbadbbbbacddccadbbaddacaddcdbbbdcdbcbbdaaacadbccbabbbaacbcbaababbbabcdac...

output:

27
ddc

result:

ok 2 lines

Test #10:

score: 0
Accepted
time: 4ms
memory: 30432kb

input:

1000
bbccbcaaccbcdccaacbbcbadbabadddaabacadadacbbdacabdbdcaaaddabbabcacbddcdaccbcbcbddcabbbadacaaabcacbaabaccaccbdbbcddbddcadbbabaadcdccbbaacdbaddacaccbbabdacdbbbddccbcdbaccbbcddbbbddaaadccacdddddccbbbdcdadabbbcccbbbdddacbabacdccbdcdbdaacdabaaaccbbccdcddcdcdbcacacccdbabcaaadabbddcdbdbaacaaddcbcbbccb...

output:

24
bab

result:

ok 2 lines

Test #11:

score: 0
Accepted
time: 29ms
memory: 90680kb

input:

931528
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

310509
aaa

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 19ms
memory: 71100kb

input:

615161
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205053
aaa

result:

ok 2 lines

Test #13:

score: 0
Accepted
time: 23ms
memory: 72688kb

input:

623944
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

200880
aaa

result:

ok 2 lines

Test #14:

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

input:

1000000
baabaabbaaaabbababbbabbbabaabbbaaaabaabbababbbbaabbaabbabbbbbbbaaaaabbbbbababaaababbbaababbbbbbaababbbaaabbbbbbbbababbbbabbbbabbbbbbbaabaaabbaaaaaaaaabbabababbabbbbaabbbbbaaabbbbabbbbaababbabaaaaaababbbaabbabbbbaaaabbbbaabbababaababbababbbbaaaabbbbabbaaabbbbaabaaaabbbbbaababaaabbbabaabababba...

output:

191420
aab

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 70ms
memory: 57664kb

input:

1000000
aabbbbbcbacccabaaaccccaacaccccbcaabacaaabacccabbcaccaaacbaabcbacbcaaababacbbacaabcbaaacbbaaaaaabbaaabbcbaabaccaacccacbbaabbaaaaaabbaccbcaabcabcacabcaacbacaccbbcbbbccbbbcaacbaabcacacccbcbacaccaaaccabaaccbbcbbbcbcabbcbabbabacbbbcbbbcacbcabbaaacbaaaccbacacabcccbbabaccaccbcbbccacbbabbbacacabaccc...

output:

40521
ccb

result:

ok 2 lines

Test #16:

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

input:

1000000
acdbcbcccdddcccdccadbdcccaaacbbdadbdacacaadcadadccdbbacdbcbddadabbdcbccbcadadbaddabdbadbbdcbcdcabbdabadabaaaddbcdbbaddcaadbcbcdacdbaacdbddbdacaaacadbbcadadacdbdcdcdccddbdddccacacbbcbbccacbdbbbdbcddbdcaccdcdcdbababbdbcbcacddddaadadcdcbbacbbdbddaadbbbbcccccabbadddbbbaaaddccdaadcaddbbdcdcdaabaa...

output:

16769
abd

result:

ok 2 lines

Test #17:

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

input:

1000000
abbaccdaecaaeadcaabecddbdedbcbebeeaeabaaaacedcaaabbbcabcbddcdcececcceacacaedeebaddabcdedeadbacabbbaadbeeeebbdaeadcacadadddbdbcaeeeaeddaccdceacebbaabccacdbdacdbcabaeeddeccecdcaeedbadbceebbcddbbeeecdeceabbdccccadcbeedacadceabadabcbcbbecddacbcbbbbbbadbacbdbcdbecadeecbeabceccabccdecccdbdcdbbeeee...

output:

8338
dce

result:

ok 2 lines

Test #18:

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

input:

1000000
abbbbbbabbababbbbaabababbbaaaaabbabbaaabababaaaababbbaaaabaababaaababbbaabbbbbbbaaaaabaabbabaabaaabaababaaabbabaaaaabbbbaabaababbbbbbbabaabaaabbabbbaaababaababababbbaababbaabbbbbaaabbaabbbbabbaabaababbaabbbabaaaabbababaabbabbabbabaabbbbaaababbbbbaaaabaaabbaabaaabaabbaabaaabaabaabbbaaaaabbbab...

output:

191383
bba

result:

ok 2 lines

Test #19:

score: 0
Accepted
time: 68ms
memory: 57428kb

input:

1000000
aabbcbcaabbabccabbbccabbcbacabccccccbbbcbccbabacacaccccbcbcbacaaaababbbabacacbbccaacbaacbacccabbabbbccbcbbbcbbacacaccbbaacbaaabaabbaccacccbcbbcacbbacabaabbabcacccaccbcacccccccbcbacaabbcbaaabaaabcabbaacabaaaaaccbabaabccbaabacbbcbbaabcbccccbcaccbbbccbbbbaabacbacbbaacbcccccbabacacbcccaaaccccaca...

output:

40925
caa

result:

ok 2 lines

Test #20:

score: 0
Accepted
time: 77ms
memory: 97696kb

input:

1000000
babbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabb...

output:

333333
abb

result:

ok 2 lines

Test #21:

score: 0
Accepted
time: 73ms
memory: 57240kb

input:

999986
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefg...

output:

38461
abc

result:

ok 2 lines

Test #22:

score: 0
Accepted
time: 3ms
memory: 33212kb

input:

5388
xxyzyzaaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwabcabdabeabfabgabhabiabjabkablabmabnaboabpabqabrabsabtabuabvabwacdaceacfacgachaciacjackaclacmacnacoacpacqacracsactacuacvacwadeadfadgadhadiadjadkadladmadnadoadpadqadradsadtaduadvadwaefaegaehaeiaejaekaelaemaenaeoaepaeqaera...

output:

2
xyz

result:

ok 2 lines

Test #23:

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

input:

1000000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaafaaf...

output:

87
fwu

result:

ok 2 lines

Test #24:

score: 0
Accepted
time: 1ms
memory: 33256kb

input:

6
ababaa

output:

1
aba

result:

ok 2 lines

Test #25:

score: 0
Accepted
time: 1ms
memory: 30308kb

input:

6
aababa

output:

2
aba

result:

ok 2 lines

Test #26:

score: 0
Accepted
time: 99ms
memory: 56788kb

input:

1000000
zenudggmyopddhszhrbmftgzmjorabhgojdtfnzxjkayjlkgczsyshczutkdchiytqlfsevymipufxkxojlvkkqxvjhpjmcxeiluubblcdiwjphlpzwvknsyvbcodpyktizgatrlieiikktghixbikehsiknjuateltwkyyhgabygwtclyeyquaoiqnypoxnvyzvyhfejoljxnwhkkcgitdebuutnzzvawollaiesjsnlbdvdarlewlnusmgwhulzimadkzlngoukodeljdpjpxxdljooczhewfz...

output:

90
cze

result:

ok 2 lines

Test #27:

score: 0
Accepted
time: 108ms
memory: 56748kb

input:

1000000
rtzxovxqfapkdmelxiyjroohufhbakpmmvaxqcptiwtcijcabvobzwbrespqhpvjidgmlvjetwieqngdfbinbsjyfgxofbunxgmhjnkdhhwzjaqqhxjurewcpktfzgxdheuuyfrcmqxykcxjaeotsutxkedqsoyoxzvcspgbnzrwypgdqnfbxywblqvdufggbbskburngiyxtrauvhxjeposnzhcbxlkcczhvpxdbmegacemorezpcsnlzbbiasssvhgneavpnoeikfrhkxeredmmsuowksdtoon...

output:

88
yqs

result:

ok 2 lines

Test #28:

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

input:

1000000
ljmybiqxmnqqbsoxkyvgdiupdyamxtyvhjvbdsgogfkgghvubrlefmxiorufmakswraubnxjakandedlvsfepzcxnelmzqkeqbqrawwukmicllbvauvtzuajjsmxuuuzvypgzstvpbmpktcluzglzelpaayvyhwkqmzixfotvxjsohrctbgdezsorqehyxozheoxcgcwcellqwdhgdqjxkyiaetlntxbfgkehdlfkoococgfziqkcibndisxwwsanicoxybhrtpphfibclqqbtmaxbendpnagfxb...

output:

87
qfh

result:

ok 2 lines

Test #29:

score: 0
Accepted
time: 103ms
memory: 56788kb

input:

1000000
fyyymvhdtbqyaxbiypqdqdaykusyvdgccwsfohwjgrckffnqanhhkaubwqzsrjzcleuatejofztxpvaqmidwghvywbbltfcujzrerfgjoowflukcusivimfoedcoqlstisjtzfvmtnbhllflpuyfhoagswuyfbufmzbncwvocvzngafbvnkfkbrcutmldoxqnikmdtodzzzzmchstallsfjwmjhszqiqhmwcrsaftrzvebgwhydynoiotqhqkrqhgxxufscrvapaebmmxljfiiuoiiomnxhwwxgp...

output:

92
nsk

result:

ok 2 lines

Test #30:

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

input:

1000000
zokbxiahaosfyclumgnaczggrnljumplxknibxmeedvnefhkygdkqosshpegwunnzsohmxxumnnhckwyczaowpoxezqlovukcuuqgrsbrtifngthlquuqdjvyltgjbrmwoefypvdyzqwlainjoqxrzrwktnblvszfndrjodikurlytsayblhpdnrytxnhfejtjfzeeamttmnjgkffwelozvmyosbmoufjpjzbeohbulotcinspqmyurolxwlwloobkszpnddxhrkbxoytmdsqxaetqzmufcslqpd...

output:

89
ynq

result:

ok 2 lines

Extra Test:

score: 0
Extra Test Passed