QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#684099#9522. A Simple String Problemucup-team918AC ✓297ms47776kbC++173.2kb2024-10-28 10:21:132024-10-28 15:18:53

Judging History

你现在查看的是测评时间为 2024-10-28 15:18:53 的历史记录

  • [2024-11-10 22:37:16]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:312ms
  • 内存:46932kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:48:45]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:340ms
  • 内存:46832kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-28 15:18:53]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:297ms
  • 内存:47776kb
  • [2024-10-28 15:17:17]
  • hack成功,自动添加数据
  • (/hack/1080)
  • [2024-10-28 14:31:18]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:305ms
  • 内存:47776kb
  • [2024-10-28 14:28:57]
  • hack成功,自动添加数据
  • (/hack/1079)
  • [2024-10-28 10:21:13]
  • 评测
  • 测评结果:100
  • 用时:294ms
  • 内存:47092kb
  • [2024-10-28 10:21:13]
  • 提交

answer

#include <bits/stdc++.h>
#define cerr cout << "in " << __LINE__ << "\t: "
using namespace std;
#define lg(x) (31 ^ __builtin_clz(x))
int n;
string s[2], t;
const int N = 400010;
int m = 128, old[N << 1], rk[N], sa[N], cnt[N], key[N], key2[N], h[N];
int st[20][N];
int LCP(int x, int y) {
	x = rk[x], y = rk[y];
	if (x > y) swap(x, y);
	int len = lg(y - (x++));
	return min(st[len][x], st[len][y - (1 << len) + 1]);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> s[0] >> s[1];
	t = s[0] + '#' + s[1] + '*', n = n * 2 + 1;
	for (int i = 1; i <= n; i++) cnt[rk[i] = t[i - 1]]++;
	for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
	for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
	for (int w = 1;; w <<= 1) {
		int p = 0;
		for (int i = n; i > n - w; i--) key2[++p] = i;
		for (int i = 1; i <= n; i++)
			if (sa[i] > w) key2[++p] = sa[i] - w;
		memset(cnt, 0, sizeof(cnt));
		for (int i = 1; i <= n; i++) cnt[key[i] = rk[key2[i]]]++;
		for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		memcpy(old, rk, sizeof(rk));
		for (int i = n; i > 0; i--) sa[cnt[key[i]]--] = key2[i];
		p = 0;
		for (int i = 1; i <= n; i++) {
			int x = sa[i], y = sa[i - 1];
			rk[sa[i]] = p += old[x] != old[y] || old[x + w] != old[y + w];
		}
		if ((m = p) == n) break;
	}
	for (int i = 1, k = 0; i <= n; ++i) {
		if (rk[i] == 1) continue;
		if (k) --k;
		while (t[i + k - 1] == t[sa[rk[i] - 1] + k - 1]) ++k;
		h[rk[i]] = k;
	}
	for (int i = 1; i <= n; i++)
		st[0][i] = h[i];
	for (int i = 1; i < 20; i++)
		for (int j = 1; j + (1 << i) - 1 <= n; j++)
			st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
	n /= 2;
	int res = 0;
	for (int i = 1; i <= (n + 1) / 2; i++) {
		for (int j = 1; j <= n; j += max(1, i - 1)) {
			if (j + i > n) continue;
			int tmp = LCP(j, j + i);
			if (tmp == 0) continue;
			if (tmp >= i) {res = i * 2; continue;}
			int tmp2 = LCP(j + tmp, j + tmp + i + n);
			if (tmp + tmp2 >= i) {res = i * 2; continue;}
			int l = j - (i - tmp - tmp2);
			if (l > 0 && LCP(l, l + i) >= i - tmp - tmp2) res = i * 2;
		}
		for (int j = 1; j <= n; j += max(1, i - 1)) {
			if (j + i > n) continue;
			int tmp = LCP(j + n + 1, j + i + n + 1);
			if (tmp == 0) continue;
			if (tmp >= i) {res = i * 2; continue;}
			int l = j - (i - tmp);
			if (l < 0) continue;
			int tmp2 = LCP(l + 1, l + n + 1 + i);
			if (tmp2 >= i - tmp) {res = i * 2; continue;}
			if (l + tmp2 <= 0) continue;
			if (LCP(l + 1 + tmp2 + n, l + 1 + tmp2 + n + i) >= i - tmp - tmp2) res = i * 2;
		}
		for (int j = 1; j <= n; j += max(1, i - 1)) {
			if (j + i - 1 > n) continue;
			int tmp = LCP(j, j + i + n);
			if (tmp == 0) continue;
			if (tmp >= i) {res = i * 2; continue;}
			int tmp2 = LCP(j + tmp + n, j + i + tmp + n);
			if (tmp2 >= i - tmp) {res = i * 2; continue;}
			int l = j - (i - tmp - tmp2);
			if (l > 0 && LCP(l, l + i + n) >= i - tmp - tmp2)
				{res = i * 2; continue;}
			l = j - (i - tmp);
			if (l <= 0) continue;
			tmp2 = LCP(l, l + i);
			if (tmp2 >= i - tmp) {res = i * 2; continue;}
			if (LCP(l + tmp2, l + tmp2 + i + n) >= i - tmp) res = i * 2;
		}
	}
	cout << res << "\n";
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 178ms
memory: 46184kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 172ms
memory: 46520kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 180ms
memory: 45368kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 195ms
memory: 45644kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 226ms
memory: 46404kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 297ms
memory: 47116kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

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

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed