QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#679073#9522. A Simple String Problemucup-team4504#AC ✓542ms85760kbC++143.3kb2024-10-26 16:48:092024-10-26 16:48:10

Judging History

你现在查看的是测评时间为 2024-10-26 16:48:10 的历史记录

  • [2024-11-10 22:36:38]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:567ms
  • 内存:85512kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:48:14]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:519ms
  • 内存:85468kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-28 15:17:49]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:799ms
  • 内存:85616kb
  • [2024-10-28 15:17:17]
  • hack成功,自动添加数据
  • (/hack/1080)
  • [2024-10-28 14:29:44]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:909ms
  • 内存:85300kb
  • [2024-10-28 14:28:57]
  • hack成功,自动添加数据
  • (/hack/1079)
  • [2024-10-27 18:37:36]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:570ms
  • 内存:85676kb
  • [2024-10-27 18:36:42]
  • hack成功,自动添加数据
  • (/hack/1075)
  • [2024-10-26 16:48:10]
  • 评测
  • 测评结果:100
  • 用时:542ms
  • 内存:85760kb
  • [2024-10-26 16:48:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
const int N = 4e5 + 5;
int n;
char a[N], b[N];
struct SA{
	int n, sa[N], rk[N], tot, t[N], y[N], _r[N];
	int height[N];
	char c[N];
	int log2n, st[25][N];
	void getsa(){
		vector<pair<int, int>> vec;
		for (int i = 1; i <= n; i++) vec.emplace_back(c[i], i);
		sort(vec.begin(), vec.end());
		for (int i = 1; i <= n; i++) sa[i] = vec[i - 1].second;
		for (int i = 1; i <= n; i++) rk[sa[i]] = rk[sa[i - 1]] + (c[sa[i]] != c[sa[i - 1]]);
		for (int step = 1; step <= n; step <<= 1){
			tot = 0;
			for (int i = n - step + 1; i <= n; i++) y[++tot] = i;
			for (int i = 1; i <= n; i++)
				if (sa[i] > step)
					y[++tot] = sa[i] - step;
			memset(t, 0, sizeof(t));
			for (int i = 1; i <= n; i++) t[rk[i]]++;
			for (int i = 1; i <= n; i++) t[i] += t[i - 1];
			for (int i = n; i >= 1; i--) sa[t[rk[y[i]]]--] = y[i];
			memcpy(_r, rk, sizeof(_r));
			for (int i = 1; i <= n; i++) rk[sa[i]] = rk[sa[i - 1]] + (_r[sa[i]] != _r[sa[i - 1]] || _r[sa[i] + step] != _r[sa[i - 1] + step]);
		}
	}
	void getheight(){
		int same = 0;
		for (int i = 1; i <= n; i++){
			if (rk[i] == 1){
				same = 0;
				continue;
			}
			if (same) same--;
			int j = sa[rk[i] - 1];
			while (i + same <= n && j + same <= n && c[i + same] == c[j + same]) same++;
			height[rk[i]] = same;
		}
	}
	void getst(){
		log2n = log2(n);
		for (int i = 2; i <= n; i++) st[0][i] = height[i];
		for (int j = 1; j <= log2n; j++)
			for (int i = 2; i + (1 << j) - 1 <= n; i++)
				st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
	}
	int lcp(int i, int j){
		i = rk[i], j = rk[j];
		if (i > j) swap(i, j);
		i++;
		int t = 31 ^ __builtin_clz(j - i + 1);
		return min(st[t][i], st[t][j - (1 << t) + 1]);
	}
	void init(){
		getsa();
		getheight();
		getst();
	}
}sa1, sa2;
int lcppre(int a, int b, int p1, int p2){
	p1 += a * n;
	p2 += b * n;
	return sa1.lcp(p1, p2);
}
int lcpsuf(int a, int b, int p1, int p2){
	p1 = 2 * n - p1 + 1;
	p2 = 2 * n - p2 + 1;
	p1 -= a * n;
	p2 -= b * n;
	return sa2.lcp(p1, p2);
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	cin >> n >> (a + 1) >> (b + 2);
	a[n + 1] = '?';
	n++;
	b[1] = '&';
	sa1.n = sa2.n = n * 2;
	for (int i = 1; i <= n * 2; i++){
		sa1.c[i] = i <= n ? a[i] : b[i - n];
		sa2.c[i] = i <= n ? b[n - i + 1] : a[n - (i - n) + 1];
	}
	sa1.init();
	sa2.init();
	for (int i = n; i >= 1; i--){
		bool flg = 0;
		for (int j = i; j <= n; j += i){
			{
				int len2 = lcpsuf(0, 0, j, j - i);
				int len1 = lcppre(0, 0, j - i + 1, j + 1);
				int len11 = lcppre(0, 1, j - i + 1 + len1, j + 1 + len1);
				if (len2 + len1 + len11 >= i) flg = 1;
			}
			{
				int len2 = lcpsuf(1, 1, j, j - i);
				int len1 = lcppre(1, 1, j - i + 1, j + 1);
				int len22 = lcpsuf(1, 0, j - len2, j - i - len2);
				if (len2 + len22 + len1 >= i) flg = 1;
			}
			{
				int len2 = lcpsuf(1, 0, j, j - i);
				int len1 = lcppre(0, 1, j - i + 1, j + 1);
				int len22 = lcpsuf(0, 0, j - len2, j - i - len2);
				int len11 = lcppre(1, 1, j - i + 1 + len1, j + 1 + len1);
				if (len2 + len1 + max(len22, len11) >= i) flg = 1;
			}
		}
		if (flg){
			cout << i * 2;
			return 0;
		}
	}
	cout << 0;
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 34808kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

score: 0
Accepted
time: 6ms
memory: 32476kb

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 343ms
memory: 85572kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 337ms
memory: 85760kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 350ms
memory: 83364kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 433ms
memory: 85592kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 239ms
memory: 84488kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 262ms
memory: 85596kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 542ms
memory: 83544kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 6ms
memory: 34356kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 4ms
memory: 42532kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 4ms
memory: 44612kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed