QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694889#9522. A Simple String ProblemGrand_ElfAC ✓560ms101844kbC++173.6kb2024-10-31 18:53:272024-10-31 18:53:32

Judging History

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

  • [2024-11-10 22:38:05]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:543ms
  • 内存:101864kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:49:43]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:879ms
  • 内存:101912kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-31 18:53:32]
  • 评测
  • 测评结果:100
  • 用时:560ms
  • 内存:101844kb
  • [2024-10-31 18:53:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;

int n, ans, lg[N];
string s, t;

struct SA {
	int m, p, a[N], rk[N], sa[N], cnt[N], id[N], nrk[N], ht[N], f[N][20];

	void work(string s) {
		m = s.size();
		for (int i = 1; i <= m; i++) {
			a[i] = s[i];
		}
		for (int i = 1; i <= 127; i++) {
			cnt[i] = 0;
		}
		for (int i = 1; i <= m; i++) {
			cnt[a[i]]++;
		}
		for (int i = 1; i <= 127; i++) {
			cnt[i] += cnt[i - 1];
		}
		for (int i = 1; i <= m; i++) {
			sa[cnt[a[i]]--] = i;
		}
		p = 0;
		for (int i = 1; i <= m; i++) {
			rk[sa[i]] = a[sa[i]] == a[sa[i - 1]] ? p : ++p;
		}
		for (int w = 1; ; w <<= 1) {
			for (int i = 1; i <= p; i++) {
				cnt[i] = 0;
			}
			for (int i = 1; i <= m; i++) {
				cnt[rk[i]]++;
			}
			for (int i = 1; i <= p; i++) {
				cnt[i] += cnt[i - 1];
			}
			p = 0;
			for (int i = 0; i < w; i++) {
				id[++p] = m - i;
			}
			for (int i = 1; i <= m; i++) {
				if (sa[i] > w) {
					id[++p] = sa[i] - w;
				}
			}
			for (int i = p; i >= 1; i--) {
				sa[cnt[rk[id[i]]]--] = id[i];
			}
			p = 0;
			for (int i = 1; i <= m; i++) {
				nrk[sa[i]] = rk[sa[i]] == rk[sa[i - 1]] && rk[sa[i] + w] == rk[sa[i - 1] + w] ? p : ++p;
			}
			for (int i = 1; i <= m; i++) {
				rk[i] = nrk[i];
			}
			if (p == m) {
				break;
			}
		}
		for (int i = 1, k = 0; i <= m; i++) {
			if (k) {
				k--;
			}
			while (a[i + k] == a[sa[rk[i] - 1] + k]) {
				k++;
			}
			ht[rk[i]] = k;
		}
		for (int i = 1; i <= m; i++) {
			f[i][0] = ht[i];
		}
		for (int j = 1; 1 << j <= m; j++) {
			for (int i = 1; i + (1 << j) - 1 <= m; i++) {
				f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
			}
		}
	}

	int query(int i, int j) {
		int k = lg[j - i + 1];
		return min(f[i][k], f[j - (1 << k) + 1][k]);
	}

	int lcp(int i, int j) {
		int x = rk[i], y = rk[j];
		if (x > y) {
			swap(x, y);
		}
		return query(x + 1, y);
	}
} S, T;

int main() {
	// freopen("d.in", "r", stdin);
	// freopen("d.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	for (int i = 2; i <= N - 5; i++) {
		lg[i] = lg[i / 2] + 1;
	}
	cin >> n >> s >> t;
	n++;
	s = s + t.back();
	t = s.front() + t;
	S.work('A' + s + 'B' + t + 'C');
	reverse(s.begin(), s.end());
	reverse(t.begin(), t.end());
	T.work('A' + s + 'B' + t + 'C');
	reverse(s.begin(), s.end());
	reverse(t.begin(), t.end());
	for (int len = n / 2; len >= 1; len--) {
		for (int i = len * 2; i <= n; i += len) {
			int j = i - len;
			if (T.lcp(n - j + 1, n - i + 1) + S.lcp(j + 1, i + 1) >= len || T.lcp(n + 1 + n - j + 1, n + 1 + n - i + 1) + 
				S.lcp(n + 1 + j + 1, n + 1 + i + 1) >= len || T.lcp(n - j + 1, n + 1 + n - i + 1) + 
				S.lcp(j + 1, n + 1 + i + 1) >= len) {
				ans = max(ans, len);
				break;
			} else {
				int s = T.lcp(n - j + 1, n + 1 + n - i + 1);
				int p = S.lcp(j + 1, n + 1 + i + 1);
				if (j - s >= 1 && T.lcp(n - (j - s) + 1, n - (i - s) + 1) >= len - s - p) {
					ans = max(ans, len);
					break;
				}
				if (i + 1 + p <= n && S.lcp(n + 1 + j + 1 + p, n + 1 + i + 1 + p) >= len - s - p) {
					ans = max(ans, len);
					break;
				}
				s = T.lcp(n + 1 + n - j + 1, n + 1 + n - i + 1);
				p = S.lcp(n + 1 + j + 1, n + 1 + i + 1);
				if (j - s >= 1 && T.lcp(n - (j - s) + 1, n + 1 + n - (i - s) + 1) >= len - s - p) {
					ans = max(ans, len);
					break;
				}
				s = T.lcp(n - j + 1, n - i + 1);
				p = S.lcp(j + 1, i + 1);
				if (i + 1 + p <= n && S.lcp(j + p + 1, n + 1 + i + p + 1) >= len - s - p) {
					ans = max(ans, len);
					break;
				}
			}
		}
	}
	cout << ans * 2 << '\n';

	return 0;
}

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

详细

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 532ms
memory: 101840kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 513ms
memory: 101728kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 560ms
memory: 99580kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 474ms
memory: 101652kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 420ms
memory: 99732kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 483ms
memory: 99644kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 348ms
memory: 101844kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed