QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#694957#9522. A Simple String Problem中国入民小学附属信息I队 (Zicheng Wang, Shubang Liu, Minkai Shao)#AC ✓334ms88884kbC++143.0kb2024-10-31 19:01:292024-11-10 22:38:06

Judging History

This is the latest submission verdict.

  • [2024-11-10 22:38:06]
  • 自动重测本题所有获得100分的提交记录
  • Verdict: AC
  • Time: 334ms
  • Memory: 88884kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:49:44]
  • 自动重测本题所有获得100分的提交记录
  • Verdict: 100
  • Time: 339ms
  • Memory: 88720kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-31 19:01:38]
  • Judged
  • Verdict: 100
  • Time: 355ms
  • Memory: 88568kb
  • [2024-10-31 19:01:29]
  • Submitted

answer

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

const int maxn = 4e5 + 10;

struct SA
{
	int sa[maxn], id[maxn], rk[maxn << 1], oldr[maxn << 1];
	int tmp[maxn], lg[maxn], f[19][maxn], n;
	
	char *sssss;
	
	bool cmp(int i, int j, int w) { return oldr[i] == oldr[j] && oldr[i + w] == oldr[j + w]; }
	void buildsa(char *s, int len)
	{
		n = len;
		sssss = s;
		int m = 127, p;
		for (int i = 1; i <= n; i++) tmp[rk[i] = s[i]]++;
		for (int i = 1; i <= m; i++) tmp[i] += tmp[i - 1];
		for (int i = n; i; i--) sa[tmp[rk[i]]--] = i;
		for (int j = 1; j < n; j <<= 1)
		{
			p = 0;
			for (int i = n; i > n - j; i--) id[++p] = i;
			for (int i = 1; i <= n; i++)
				if (sa[i] > j) id[++p] = sa[i] - j;
			
			for (int i = 0; i <= m; i++) tmp[i] = 0;
			for (int i = 1; i <= n; i++) tmp[rk[i]]++;
			for (int i = 1; i <= m; i++) tmp[i] += tmp[i - 1];
			for (int i = n; i; i--) sa[tmp[rk[id[i]]]--] = id[i];
			
			for (int i = 1; i <= n; i++) oldr[i] = rk[i]; p = 0;
			for (int i = 1; i <= n; i++)
				rk[sa[i]] = cmp(sa[i], sa[i - 1], j) ? p : ++p;
			if (p == n) break;
			m = p;
		}
		for (int i = 1, k = 0; i <= n; i++)
		{
			if (k) k--;
			while (s[i + k] == s[sa[rk[i] - 1] + k]) k++;
			f[0][rk[i]] = k;
		}
		
		for (int i = 1, k = 0; i <= n; i++)
		{
			if (i == (1 << (k + 1))) k++;
			lg[i] = k;
		}
		for (int i = 1; i <= 18; i++)
			for (int j = 1; j + (1 << i) - 1 <= n; j++)
				f[i][j] = min(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
	}
	
	int query(int l, int r)
	{
		l = rk[l], r = rk[r];
		if (l > r) swap(l, r); l++;
		int k = lg[r - l + 1];
		return min(f[k][l], f[k][r - (1 << k) + 1]);
	}
}S, T;

int n;
char str1[maxn], str2[maxn], s[maxn], t[maxn];

int Lcp(int x, int y) { if (x <= 0 || y > n * 2 + 1) return 0; return S.query(x, y); }
int Lcs(int x, int y) { if (x <= 0 || y > n * 2 + 1) return 0; return T.query(2 * n + 2 - x, 2 * n + 2 - y); }

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	
	cin >> n >> s + 1 >> t + 2;
	t[1] = s[1], s[n + 1] = t[n + 1]; n++;
	for (int i = 1; i <= n; i++) str1[i] = s[i], str2[i] = t[n - i + 1];
	str1[n + 1] = str2[n + 1] = '#';
	for (int i = 1; i <= n; i++) str1[i + n + 1] = t[i], str2[i + n + 1] = s[n - i + 1];
	str1[n * 2 + 2] = str2[n * 2 + 2] = 0;
	S.buildsa(str1, 2 * n + 1), T.buildsa(str2, 2 * n + 1);
	
	for (int len = n / 2; len; len--)
		for (int r = len << 1; r <= n; r += len)
		{
			int l = r - len + 1;
			int lcp = Lcp(l + n + 1, r + n + 2), lcs = Lcs(l + n, r + n + 1);
			if (lcp + lcs + Lcs(l - lcs - 1, r - lcs + n + 1) >= len) return cout << (len << 1) << "\n", 0;
			
			lcs = Lcs(l - 1, r), lcp = Lcp(l, r + 1);
			if (lcp + lcs + Lcp(l + lcp, r + lcp + n + 2) >= len) return cout << (len << 1) << "\n", 0;
			
			lcp = Lcp(l, r + n + 2), lcs = Lcs(l - 1, r + n + 1);
			if (lcp + lcs + max(Lcp(l + lcp + n + 1, r + n + 2 + lcp), Lcs(l - lcs - 1, r - lcs)) >= len) return cout << (len << 1) << "\n", 0;
		}
	cout << "0";
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 201ms
memory: 88764kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 181ms
memory: 88356kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 200ms
memory: 88584kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 334ms
memory: 88308kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 142ms
memory: 88204kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 157ms
memory: 88188kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 295ms
memory: 88884kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed