QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#712648 | #9586. 野兽节拍 | xhgua# | AC ✓ | 46ms | 23416kb | C++17 | 2.1kb | 2024-11-05 16:31:49 | 2024-11-05 16:31:50 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
struct DSU {
int n;
std::vector<int> f;
DSU (int n_ = 0) {
init(n_);
}
void init (int n_) {
int n = n_;
f.resize(n);
std::iota(f.begin(), f.end(), 0);
}
int find (int x) {
while (f[x] != x) {
x = f[x] = f[f[x]];
}
return x;
}
void merge (int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return ;
}
f[y] = x;
}
};
int main () {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::string s;
std::cin >> s;
s = ' ' + s;
std::vector<int> v[26][26][26] {};
for (int i = 1; i + 2 <= n; i++) {
v[s[i] - 'a'][s[i + 1] - 'a'][s[i + 2] - 'a'].push_back(i);
}
DSU dsu(n + 1);
std::vector<int> d(n + 1), use;
auto del = [&](int x) {
use.push_back(x);
d[x] = 1;
dsu.merge(x - 1, x);
};
int cnt = 0;
auto find = [&](int a, int b, int c) {
del(a);
del(b);
del(c);
cnt++;
};
int ans = -1;
std::array<int, 3> way = {-1, -1, -1};
for (int i = 0; i < 26; i++) {
for (int j = 0; j < 26; j++) {
for (int k = 0; k < 26; k++) {
cnt = 0;
for (int u = 0; u < v[i][j][k].size(); u++) {
int p = v[i][j][k][u];
if (d[p]) {
continue;
}
find(p, p + 1, p + 2);
int np = p + 3;
while (np <= n) {
int c1 = dsu.find(p);
if (c1 == 0) {
break;
}
int c0 = dsu.find(c1 - 1);
if (c0 != 0 && s[c0] - 'a' == i && s[c1] - 'a' == j &&
s[np] - 'a' == k) {
find(c0, c1, np);
np++;
continue;
} else if (np + 1 <= n && s[c1] - 'a' == i && s[np] - 'a' == j &&
s[np + 1] - 'a' == k) {
find(c1, np, np + 1);
np += 2;
continue;
} else {
break;
}
}
}
if (ans < cnt) {
ans = cnt;
way = {i, j, k};
}
for (int x : use) {
dsu.f[x] = x;
d[x] = 0;
}
use.clear();
}
}
}
std::cout << ans << "\n";
for (int i = 0; i < 3; i++) {
std::cout << char(way[i] + 'a');
}
std::cout << "\n";
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4040kb
input:
10 aaababbaab
output:
3 aab
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 4028kb
input:
14 liaoningdalian
output:
2 lia
result:
ok 2 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
3 zyl
output:
1 zyl
result:
ok 2 lines
Test #4:
score: 0
Accepted
time: 23ms
memory: 16192kb
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabababababababababababababababababaaaaaaaaaaaaaaaaaacacacacacacacacacacacacacacacacacaaaaaaaaaaaaaaaaaadadadadadadadadadadadadadadadadadaaaaaaaaaaaaaaaaaaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaeaaaaaaaaaaaaaaaaaafafafafafafafafafafa...
output:
3717 aaa
result:
ok 2 lines
Test #5:
score: 0
Accepted
time: 34ms
memory: 17328kb
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaababaaaaaaabababababaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaacacacacaaaaacacacacacacacaaacaaaaaaaaaaaaaaaaaadadaaaaaaaaadaaadadaaaaadaaaaadadaaaaaaaaaaaaaaaaaaaaaaeaeaaaaaeaaaaaaaeaeaeaaaaaaaeaaaaaaaaaaaaaaaaaaaafaaaaaaafafafafafa...
output:
7571 xxx
result:
ok 2 lines
Test #6:
score: 0
Accepted
time: 32ms
memory: 16412kb
input:
896376 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaababaaaaaaaaabaaabaaaaaaaaababaaaaaaaaaaaaaaaaaaaaaaaaaacaaaaacaaaaaaaaacacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaadaaaaaaaaaaaaaaaaaaaaadaaaaadaaaaaaaaaaaaaaaaaaaaeaeaeaaaaaeaaaaaeaaaaaeaeaaaeaeaaaaaaaaaaaaaaaaaafafaaafafaaaaaaaaaaa...
output:
6680 xxx
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 27ms
memory: 14376kb
input:
667888 eqjszvsxnlvgskosbdoyavaooutvfysniyfplykvmcnsgaomyeqqokqsrdykzfbzsbtkvotfsmmjgkhjhhxbgntmdzmxmexstdwwjrtsmumrrcvkeoluhcpvazdnoxscqibnyytrryywasediqzfsptsxggweogoxeoxhtxaynefaoscgobuxcprquxqzhircomstyufqkfdykbbuibknkjeyebhssdtqbxsdbqiwgseiaezqldbswtpdziicnnwvmxcozqttffglgefiwzdkbfnqmiuicjdcdodx...
output:
63 uzb
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 4060kb
input:
1000 baddacbabcddacdcbacaccbadddbadbdaddcdabbbcccdaaaddbadcdbddccadbbddcccaaadacdcbcbbccccabdbcbcdadacadcbcdbdbcddccddbbabdcabdabadddbbdacabdbbdddddaacdabdddddddbddbdcbadbcaaddccdbcbddaccdacbdaabbabababdcabdadddbacabcdbcddcdacaaddddbaccbbcbaacbcdcbbcdaacbaddcbcbcadaabacadadbaaababbccaddaccddbccdcbca...
output:
26 ddc
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 1ms
memory: 4248kb
input:
1000 ddcddcbbbcabbbbbccbaaddcbaaddcabbabbabdaacdcdbacbddabccddcadcaccadbaddcbcdccbddabccadadcdddbaaacdacadadddadacccbbddcacccccaccacccadbbacacbdccdbccdaabdabdabbddacdccdbaacdddcdbadabddbddbddbabcccdccbcddcdbbbcaaacbcdcdbdccabbdbcbadbbbbacddccadbbaddacaddcdbbbdcdbcbbdaaacadbccbabbbaacbcbaababbbabcdac...
output:
27 ddc
result:
ok 2 lines
Test #10:
score: 0
Accepted
time: 1ms
memory: 3992kb
input:
1000 bbccbcaaccbcdccaacbbcbadbabadddaabacadadacbbdacabdbdcaaaddabbabcacbddcdaccbcbcbddcabbbadacaaabcacbaabaccaccbdbbcddbddcadbbabaadcdccbbaacdbaddacaccbbabdacdbbbddccbcdbaccbbcddbbbddaaadccacdddddccbbbdcdadabbbcccbbbdddacbabacdccbdcdbdaacdabaaaccbbccdcddcdcdbcacacccdbabcaaadabbddcdbdbaacaaddcbcbbccb...
output:
24 bab
result:
ok 2 lines
Test #11:
score: 0
Accepted
time: 13ms
memory: 23416kb
input:
931528 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
310509 aaa
result:
ok 2 lines
Test #12:
score: 0
Accepted
time: 6ms
memory: 18192kb
input:
615161 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
205053 aaa
result:
ok 2 lines
Test #13:
score: 0
Accepted
time: 3ms
memory: 19844kb
input:
623944 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaacaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
200880 aaa
result:
ok 2 lines
Test #14:
score: 0
Accepted
time: 32ms
memory: 22036kb
input:
1000000 baabaabbaaaabbababbbabbbabaabbbaaaabaabbababbbbaabbaabbabbbbbbbaaaaabbbbbababaaababbbaababbbbbbaababbbaaabbbbbbbbababbbbabbbbabbbbbbbaabaaabbaaaaaaaaabbabababbabbbbaabbbbbaaabbbbabbbbaababbabaaaaaababbbaabbabbbbaaaabbbbaabbababaababbababbbbaaaabbbbabbaaabbbbaabaaaabbbbbaababaaabbbabaabababba...
output:
191420 aab
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 35ms
memory: 19100kb
input:
1000000 aabbbbbcbacccabaaaccccaacaccccbcaabacaaabacccabbcaccaaacbaabcbacbcaaababacbbacaabcbaaacbbaaaaaabbaaabbcbaabaccaacccacbbaabbaaaaaabbaccbcaabcabcacabcaacbacaccbbcbbbccbbbcaacbaabcacacccbcbacaccaaaccabaaccbbcbbbcbcabbcbabbabacbbbcbbbcacbcabbaaacbaaaccbacacabcccbbabaccaccbcbbccacbbabbbacacabaccc...
output:
40521 ccb
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 41ms
memory: 17320kb
input:
1000000 acdbcbcccdddcccdccadbdcccaaacbbdadbdacacaadcadadccdbbacdbcbddadabbdcbccbcadadbaddabdbadbbdcbcdcabbdabadabaaaddbcdbbaddcaadbcbcdacdbaacdbddbdacaaacadbbcadadacdbdcdcdccddbdddccacacbbcbbccacbdbbbdbcddbdcaccdcdcdbababbdbcbcacddddaadadcdcbbacbbdbddaadbbbbcccccabbadddbbbaaaddccdaadcaddbbdcdcdaabaa...
output:
16769 abd
result:
ok 2 lines
Test #17:
score: 0
Accepted
time: 38ms
memory: 17304kb
input:
1000000 abbaccdaecaaeadcaabecddbdedbcbebeeaeabaaaacedcaaabbbcabcbddcdcececcceacacaedeebaddabcdedeadbacabbbaadbeeeebbdaeadcacadadddbdbcaeeeaeddaccdceacebbaabccacdbdacdbcabaeeddeccecdcaeedbadbceebbcddbbeeecdeceabbdccccadcbeedacadceabadabcbcbbecddacbcbbbbbbadbacbdbcdbecadeecbeabceccabccdecccdbdcdbbeeee...
output:
8338 dce
result:
ok 2 lines
Test #18:
score: 0
Accepted
time: 41ms
memory: 21492kb
input:
1000000 abbbbbbabbababbbbaabababbbaaaaabbabbaaabababaaaababbbaaaabaababaaababbbaabbbbbbbaaaaabaabbabaabaaabaababaaabbabaaaaabbbbaabaababbbbbbbabaabaaabbabbbaaababaababababbbaababbaabbbbbaaabbaabbbbabbaabaababbaabbbabaaaabbababaabbabbabbabaabbbbaaababbbbbaaaabaaabbaabaaabaabbaabaaabaabaabbbaaaaabbbab...
output:
191383 bba
result:
ok 2 lines
Test #19:
score: 0
Accepted
time: 40ms
memory: 19008kb
input:
1000000 aabbcbcaabbabccabbbccabbcbacabccccccbbbcbccbabacacaccccbcbcbacaaaababbbabacacbbccaacbaacbacccabbabbbccbcbbbcbbacacaccbbaacbaaabaabbaccacccbcbbcacbbacabaabbabcacccaccbcacccccccbcbacaabbcbaaabaaabcabbaacabaaaaaccbabaabccbaabacbbcbbaabcbccccbcaccbbbccbbbbaabacbacbbaacbcccccbabacacbcccaaaccccaca...
output:
40925 caa
result:
ok 2 lines
Test #20:
score: 0
Accepted
time: 25ms
memory: 22608kb
input:
1000000 babbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabbabb...
output:
333333 abb
result:
ok 2 lines
Test #21:
score: 0
Accepted
time: 25ms
memory: 19004kb
input:
999986 abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefg...
output:
38461 abc
result:
ok 2 lines
Test #22:
score: 0
Accepted
time: 1ms
memory: 4452kb
input:
5388 xxyzyzaaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwabcabdabeabfabgabhabiabjabkablabmabnaboabpabqabrabsabtabuabvabwacdaceacfacgachaciacjackaclacmacnacoacpacqacracsactacuacvacwadeadfadgadhadiadjadkadladmadnadoadpadqadradsadtaduadvadwaefaegaehaeiaejaekaelaemaenaeoaepaeqaera...
output:
2 xyz
result:
ok 2 lines
Test #23:
score: 0
Accepted
time: 31ms
memory: 17348kb
input:
1000000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaacaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaadaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaaeaafaaf...
output:
87 fwu
result:
ok 2 lines
Test #24:
score: 0
Accepted
time: 0ms
memory: 4008kb
input:
6 ababaa
output:
1 aba
result:
ok 2 lines
Test #25:
score: 0
Accepted
time: 1ms
memory: 4200kb
input:
6 aababa
output:
2 aba
result:
ok 2 lines
Test #26:
score: 0
Accepted
time: 46ms
memory: 18576kb
input:
1000000 zenudggmyopddhszhrbmftgzmjorabhgojdtfnzxjkayjlkgczsyshczutkdchiytqlfsevymipufxkxojlvkkqxvjhpjmcxeiluubblcdiwjphlpzwvknsyvbcodpyktizgatrlieiikktghixbikehsiknjuateltwkyyhgabygwtclyeyquaoiqnypoxnvyzvyhfejoljxnwhkkcgitdebuutnzzvawollaiesjsnlbdvdarlewlnusmgwhulzimadkzlngoukodeljdpjpxxdljooczhewfz...
output:
90 cze
result:
ok 2 lines
Test #27:
score: 0
Accepted
time: 39ms
memory: 18664kb
input:
1000000 rtzxovxqfapkdmelxiyjroohufhbakpmmvaxqcptiwtcijcabvobzwbrespqhpvjidgmlvjetwieqngdfbinbsjyfgxofbunxgmhjnkdhhwzjaqqhxjurewcpktfzgxdheuuyfrcmqxykcxjaeotsutxkedqsoyoxzvcspgbnzrwypgdqnfbxywblqvdufggbbskburngiyxtrauvhxjeposnzhcbxlkcczhvpxdbmegacemorezpcsnlzbbiasssvhgneavpnoeikfrhkxeredmmsuowksdtoon...
output:
88 yqs
result:
ok 2 lines
Test #28:
score: 0
Accepted
time: 43ms
memory: 18816kb
input:
1000000 ljmybiqxmnqqbsoxkyvgdiupdyamxtyvhjvbdsgogfkgghvubrlefmxiorufmakswraubnxjakandedlvsfepzcxnelmzqkeqbqrawwukmicllbvauvtzuajjsmxuuuzvypgzstvpbmpktcluzglzelpaayvyhwkqmzixfotvxjsohrctbgdezsorqehyxozheoxcgcwcellqwdhgdqjxkyiaetlntxbfgkehdlfkoococgfziqkcibndisxwwsanicoxybhrtpphfibclqqbtmaxbendpnagfxb...
output:
87 qfh
result:
ok 2 lines
Test #29:
score: 0
Accepted
time: 44ms
memory: 18680kb
input:
1000000 fyyymvhdtbqyaxbiypqdqdaykusyvdgccwsfohwjgrckffnqanhhkaubwqzsrjzcleuatejofztxpvaqmidwghvywbbltfcujzrerfgjoowflukcusivimfoedcoqlstisjtzfvmtnbhllflpuyfhoagswuyfbufmzbncwvocvzngafbvnkfkbrcutmldoxqnikmdtodzzzzmchstallsfjwmjhszqiqhmwcrsaftrzvebgwhydynoiotqhqkrqhgxxufscrvapaebmmxljfiiuoiiomnxhwwxgp...
output:
92 nsk
result:
ok 2 lines
Test #30:
score: 0
Accepted
time: 44ms
memory: 18576kb
input:
1000000 zokbxiahaosfyclumgnaczggrnljumplxknibxmeedvnefhkygdkqosshpegwunnzsohmxxumnnhckwyczaowpoxezqlovukcuuqgrsbrtifngthlquuqdjvyltgjbrmwoefypvdyzqwlainjoqxrzrwktnblvszfndrjodikurlytsayblhpdnrytxnhfejtjfzeeamttmnjgkffwelozvmyosbmoufjpjzbeohbulotcinspqmyurolxwlwloobkszpnddxhrkbxoytmdsqxaetqzmufcslqpd...
output:
89 ynq
result:
ok 2 lines
Extra Test:
score: 0
Extra Test Passed