QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#712648#9586. 野兽节拍xhgua#AC ✓46ms23416kbC++172.1kb2024-11-05 16:31:492024-11-05 16:31:50

Judging History

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

  • [2024-11-05 16:31:50]
  • 评测
  • 测评结果:AC
  • 用时:46ms
  • 内存:23416kb
  • [2024-11-05 16:31:49]
  • 提交

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