QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#711076#9586. 野兽节拍SulfoxAC ✓121ms63196kbC++203.2kb2024-11-05 00:14:292024-11-05 00:14:30

Judging History

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

  • [2024-11-05 00:14:30]
  • 评测
  • 测评结果:AC
  • 用时:121ms
  • 内存:63196kb
  • [2024-11-05 00:14:29]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
struct node {
    char c;
    int tag;
    node *pre, *nxt, *dpre, *dnxt;
    node () {c='?';tag=-1;pre=NULL;nxt=NULL;dpre=NULL;dnxt=NULL;}
};
int n;
vector<node*> g[30][30][30];
node *head = new node(), *tail = new node();
string s;

int ctag(int i, int j, int k) {
    return i * 26 * 26 + j * 26 + k;
}

void ptag(int i, int j, int k, node *a, node *b, node *c) {
    int tag = ctag(i, j, k);
    a->tag = b->tag = c->tag = tag;
    return ;
}

bool check(int i, int j, int k, node *a, node *b, node *c) {
    int tag = ctag(i, j, k);
    if(a->tag == tag || b->tag == tag || c->tag == tag) return false;
    if(a->c == (char)('a' + i) && b->c == (char)('a' + j) && c->c == (char)('a' + k)) return true;
    return false;
}

void solve() {
    cin >> n;
    
    if (n <= 2) {
        cout << 0 << endl;
        cout << "aaa" << endl;
        return;
    }
    
    cin >> s;

    head->nxt = tail;
    tail->pre = head;


    for(int i = 0; i < s.size(); i ++ ) {
        node *p = new node();
        p->c = s[i];
        p->pre = tail->pre;
        p->nxt = tail;
        tail->pre->nxt = p;
        tail->pre = p;
        if(i + 2 < s.size()) {
            g[s[i] - 'a'][s[i + 1] - 'a'][s[i + 2] - 'a'].push_back(p);
        }
    }

    int ans = 0;
    string str;


    for(int i = 0; i < 26; i ++ ) {
        for(int j = 0; j < 26; j ++ ) {
            for(int k = 0; k < 26; k ++ ) {
                int res = 0;
                for(auto x : g[i][j][k]) {
                    auto p = x, q = x->nxt;
                    int tag = ctag(i, j, k);
                    while(p != head && q != tail && p->tag != tag && q->tag != tag) {
                        if(check(i, j, k, p, q, q->nxt)) {
                            auto tp = p, tq = q->nxt;
                            ptag(i, j, k, p, q, q->nxt);
                            p = tp->pre->tag == tag ? tp->dpre : tp->pre;
                            q = tq->nxt;
                            q->dpre = p;
                            res ++ ;
                        }else if(check(i, j, k, p->pre->tag == tag ? p->dpre : p->pre, p, q)) {
                            auto tp = p->pre->tag == tag ? p->dpre : p->pre, tq = q;
                            ptag(i, j, k, p->pre->tag == tag ? p->dpre : p->pre, p, q);
                            p = tp->pre->tag == tag ? tp->dpre : tp->pre;
                            q = tq->nxt;
                            q->dpre = p;
                            res ++ ;
                        } else {
                            q->dpre = p;
                            break;
                        }
                    }
                }
                if(res > ans) {
                    ans = res;
                    str = "";
                    str.push_back(i + 'a');
                    str.push_back(j + 'a');
                    str.push_back(k + 'a');
                }
            }
        }
    }

    cout << ans << "\n" << str << "\n";
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for(int i = 1; i <= t; i ++ ) {
        solve();
    }
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3664kb

input:

10
aaababbaab

output:

3
aab

result:

ok 2 lines

Test #2:

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

input:

14
liaoningdalian

output:

2
lia

result:

ok 2 lines

Test #3:

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

input:

3
zyl

output:

1
zyl

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 36ms
memory: 55136kb

input:

896376
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabababababababababababababababababaaaaaaaaaaaaaaaaaacacacacacacacacacacacacacacacacacaaaaaaaaaaaaaaaaaadadadadadadadadadadadadadadadadadaaaaaaaaaaaaaaaaaaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaaaaaaaaaaaaaaaaaafafafafafafafafafafa...

output:

3717
aaa

result:

ok 2 lines

Test #5:

score: 0
Accepted
time: 47ms
memory: 56180kb

input:

896376
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaababaaaaaaabababababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaacacacacaaaaacacacacacacacaaacaaaaaaaaaaaaaaaaaadadaaaaaaaaadaaadadaaaaadaaaaadadaaaaaaaaaaaaaaaaaaaaaaeaeaaaaaeaaaaaaaeaeaeaaaaaaaeaaaaaaaaaaaaaaaaaaaafaaaaaaafafafafafa...

output:

7571
xxx

result:

ok 2 lines

Test #6:

score: 0
Accepted
time: 42ms
memory: 55800kb

input:

896376
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaababaaaaaaaaabaaabaaaaaaaaababaaaaaaaaaaaaaaaaaaaaaaaaaacaaaaacaaaaaaaaacacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaadaaaaadaaaaaaaaaaaaaaaaaaaaeaeaeaaaaaeaaaaaeaaaaaeaeaaaeaeaaaaaaaaaaaaaaaaaafafaaafafaaaaaaaaaaa...

output:

6680
xxx

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 47ms
memory: 44972kb

input:

667888
eqjszvsxnlvgskosbdoyavaooutvfysniyfplykvmcnsgaomyeqqokqsrdykzfbzsbtkvotfsmmjgkhjhhxbgntmdzmxmexstdwwjrtsmumrrcvkeoluhcpvazdnoxscqibnyytrryywasediqzfsptsxggweogoxeoxhtxaynefaoscgobuxcprquxqzhircomstyufqkfdykbbuibknkjeyebhssdtqbxsdbqiwgseiaezqldbswtpdziicnnwvmxcozqttffglgefiwzdkbfnqmiuicjdcdodx...

output:

63
uzb

result:

ok 2 lines

Test #8:

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

input:

1000
baddacbabcddacdcbacaccbadddbadbdaddcdabbbcccdaaaddbadcdbddccadbbddcccaaadacdcbcbbccccabdbcbcdadacadcbcdbdbcddccddbbabdcabdabadddbbdacabdbbdddddaacdabdddddddbddbdcbadbcaaddccdbcbddaccdacbdaabbabababdcabdadddbacabcdbcddcdacaaddddbaccbbcbaacbcdcbbcdaacbaddcbcbcadaabacadadbaaababbccaddaccddbccdcbca...

output:

26
ddc

result:

ok 2 lines

Test #9:

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

input:

1000
ddcddcbbbcabbbbbccbaaddcbaaddcabbabbabdaacdcdbacbddabccddcadcaccadbaddcbcdccbddabccadadcdddbaaacdacadadddadacccbbddcacccccaccacccadbbacacbdccdbccdaabdabdabbddacdccdbaacdddcdbadabddbddbddbabcccdccbcddcdbbbcaaacbcdcdbdccabbdbcbadbbbbacddccadbbaddacaddcdbbbdcdbcbbdaaacadbccbabbbaacbcbaababbbabcdac...

output:

27
ddc

result:

ok 2 lines

Test #10:

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

input:

1000
bbccbcaaccbcdccaacbbcbadbabadddaabacadadacbbdacabdbdcaaaddabbabcacbddcdaccbcbcbddcabbbadacaaabcacbaabaccaccbdbbcddbddcadbbabaadcdccbbaacdbaddacaccbbabdacdbbbddccbcdbaccbbcddbbbddaaadccacdddddccbbbdcdadabbbcccbbbdddacbabacdccbdcdbdaacdabaaaccbbccdcddcdcdbcacacccdbabcaaadabbddcdbdbaacaaddcbcbbccb...

output:

24
bab

result:

ok 2 lines

Test #11:

score: 0
Accepted
time: 24ms
memory: 55304kb

input:

931528
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

310509
aaa

result:

ok 2 lines

Test #12:

score: 0
Accepted
time: 12ms
memory: 38220kb

input:

615161
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

205053
aaa

result:

ok 2 lines

Test #13:

score: 0
Accepted
time: 15ms
memory: 39128kb

input:

623944
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

200880
aaa

result:

ok 2 lines

Test #14:

score: 0
Accepted
time: 44ms
memory: 58944kb

input:

1000000
baabaabbaaaabbababbbabbbabaabbbaaaabaabbababbbbaabbaabbabbbbbbbaaaaabbbbbababaaababbbaababbbbbbaababbbaaabbbbbbbbababbbbabbbbabbbbbbbaabaaabbaaaaaaaaabbabababbabbbbaabbbbbaaabbbbabbbbaababbabaaaaaababbbaabbabbbbaaaabbbbaabbababaababbababbbbaaaabbbbabbaaabbbbaabaaaabbbbbaababaaabbbabaabababba...

output:

191420
aab

result:

ok 2 lines

Test #15:

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

input:

1000000
aabbbbbcbacccabaaaccccaacaccccbcaabacaaabacccabbcaccaaacbaabcbacbcaaababacbbacaabcbaaacbbaaaaaabbaaabbcbaabaccaacccacbbaabbaaaaaabbaccbcaabcabcacabcaacbacaccbbcbbbccbbbcaacbaabcacacccbcbacaccaaaccabaaccbbcbbbcbcabbcbabbabacbbbcbbbcacbcabbaaacbaaaccbacacabcccbbabaccaccbcbbccacbbabbbacacabaccc...

output:

40521
ccb

result:

ok 2 lines

Test #16:

score: 0
Accepted
time: 65ms
memory: 59316kb

input:

1000000
acdbcbcccdddcccdccadbdcccaaacbbdadbdacacaadcadadccdbbacdbcbddadabbdcbccbcadadbaddabdbadbbdcbcdcabbdabadabaaaddbcdbbaddcaadbcbcdacdbaacdbddbdacaaacadbbcadadacdbdcdcdccddbdddccacacbbcbbccacbdbbbdbcddbdcaccdcdcdbababbdbcbcacddddaadadcdcbbacbbdbddaadbbbbcccccabbadddbbbaaaddccdaadcaddbbdcdcdaabaa...

output:

16769
abd

result:

ok 2 lines

Test #17:

score: 0
Accepted
time: 69ms
memory: 59160kb

input:

1000000
abbaccdaecaaeadcaabecddbdedbcbebeeaeabaaaacedcaaabbbcabcbddcdcececcceacacaedeebaddabcdedeadbacabbbaadbeeeebbdaeadcacadadddbdbcaeeeaeddaccdceacebbaabccacdbdacdbcabaeeddeccecdcaeedbadbceebbcddbbeeecdeceabbdccccadcbeedacadceabadabcbcbbecddacbcbbbbbbadbacbdbcdbecadeecbeabceccabccdecccdbdcdbbeeee...

output:

8338
dce

result:

ok 2 lines

Test #18:

score: 0
Accepted
time: 43ms
memory: 58996kb

input:

1000000
abbbbbbabbababbbbaabababbbaaaaabbabbaaabababaaaababbbaaaabaababaaababbbaabbbbbbbaaaaabaabbabaabaaabaababaaabbabaaaaabbbbaabaababbbbbbbabaabaaabbabbbaaababaababababbbaababbaabbbbbaaabbaabbbbabbaabaababbaabbbabaaaabbababaabbabbabbabaabbbbaaababbbbbaaaabaaabbaabaaabaabbaabaaabaabaabbbaaaaabbbab...

output:

191383
bba

result:

ok 2 lines

Test #19:

score: 0
Accepted
time: 61ms
memory: 60856kb

input:

1000000
aabbcbcaabbabccabbbccabbcbacabccccccbbbcbccbabacacaccccbcbcbacaaaababbbabacacbbccaacbaacbacccabbabbbccbcbbbcbbacacaccbbaacbaaabaabbaccacccbcbbcacbbacabaabbabcacccaccbcacccccccbcbacaabbcbaaabaaabcabbaacabaaaaaccbabaabccbaabacbbcbbaabcbccccbcaccbbbccbbbbaabacbacbbaacbcccccbabacacbcccaaaccccaca...

output:

40925
caa

result:

ok 2 lines

Test #20:

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

input:

1000000
babbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabb...

output:

333333
abb

result:

ok 2 lines

Test #21:

score: 0
Accepted
time: 55ms
memory: 61184kb

input:

999986
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefg...

output:

38461
abc

result:

ok 2 lines

Test #22:

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

input:

5388
xxyzyzaaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwabcabdabeabfabgabhabiabjabkablabmabnaboabpabqabrabsabtabuabvabwacdaceacfacgachaciacjackaclacmacnacoacpacqacracsactacuacvacwadeadfadgadhadiadjadkadladmadnadoadpadqadradsadtaduadvadwaefaegaehaeiaejaekaelaemaenaeoaepaeqaera...

output:

2
xyz

result:

ok 2 lines

Test #23:

score: 0
Accepted
time: 53ms
memory: 61148kb

input:

1000000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaafaaf...

output:

87
fwu

result:

ok 2 lines

Test #24:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

6
ababaa

output:

1
aba

result:

ok 2 lines

Test #25:

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

input:

6
aababa

output:

2
aba

result:

ok 2 lines

Test #26:

score: 0
Accepted
time: 100ms
memory: 63024kb

input:

1000000
zenudggmyopddhszhrbmftgzmjorabhgojdtfnzxjkayjlkgczsyshczutkdchiytqlfsevymipufxkxojlvkkqxvjhpjmcxeiluubblcdiwjphlpzwvknsyvbcodpyktizgatrlieiikktghixbikehsiknjuateltwkyyhgabygwtclyeyquaoiqnypoxnvyzvyhfejoljxnwhkkcgitdebuutnzzvawollaiesjsnlbdvdarlewlnusmgwhulzimadkzlngoukodeljdpjpxxdljooczhewfz...

output:

90
cze

result:

ok 2 lines

Test #27:

score: 0
Accepted
time: 94ms
memory: 62984kb

input:

1000000
rtzxovxqfapkdmelxiyjroohufhbakpmmvaxqcptiwtcijcabvobzwbrespqhpvjidgmlvjetwieqngdfbinbsjyfgxofbunxgmhjnkdhhwzjaqqhxjurewcpktfzgxdheuuyfrcmqxykcxjaeotsutxkedqsoyoxzvcspgbnzrwypgdqnfbxywblqvdufggbbskburngiyxtrauvhxjeposnzhcbxlkcczhvpxdbmegacemorezpcsnlzbbiasssvhgneavpnoeikfrhkxeredmmsuowksdtoon...

output:

88
yqs

result:

ok 2 lines

Test #28:

score: 0
Accepted
time: 121ms
memory: 63048kb

input:

1000000
ljmybiqxmnqqbsoxkyvgdiupdyamxtyvhjvbdsgogfkgghvubrlefmxiorufmakswraubnxjakandedlvsfepzcxnelmzqkeqbqrawwukmicllbvauvtzuajjsmxuuuzvypgzstvpbmpktcluzglzelpaayvyhwkqmzixfotvxjsohrctbgdezsorqehyxozheoxcgcwcellqwdhgdqjxkyiaetlntxbfgkehdlfkoococgfziqkcibndisxwwsanicoxybhrtpphfibclqqbtmaxbendpnagfxb...

output:

87
qfh

result:

ok 2 lines

Test #29:

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

input:

1000000
fyyymvhdtbqyaxbiypqdqdaykusyvdgccwsfohwjgrckffnqanhhkaubwqzsrjzcleuatejofztxpvaqmidwghvywbbltfcujzrerfgjoowflukcusivimfoedcoqlstisjtzfvmtnbhllflpuyfhoagswuyfbufmzbncwvocvzngafbvnkfkbrcutmldoxqnikmdtodzzzzmchstallsfjwmjhszqiqhmwcrsaftrzvebgwhydynoiotqhqkrqhgxxufscrvapaebmmxljfiiuoiiomnxhwwxgp...

output:

92
nsk

result:

ok 2 lines

Test #30:

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

input:

1000000
zokbxiahaosfyclumgnaczggrnljumplxknibxmeedvnefhkygdkqosshpegwunnzsohmxxumnnhckwyczaowpoxezqlovukcuuqgrsbrtifngthlquuqdjvyltgjbrmwoefypvdyzqwlainjoqxrzrwktnblvszfndrjodikurlytsayblhpdnrytxnhfejtjfzeeamttmnjgkffwelozvmyosbmoufjpjzbeohbulotcinspqmyurolxwlwloobkszpnddxhrkbxoytmdsqxaetqzmufcslqpd...

output:

89
ynq

result:

ok 2 lines

Extra Test:

score: 0
Extra Test Passed