QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#679263#9522. A Simple String Problemucup-team5052#AC ✓413ms79788kbC++142.7kb2024-10-26 17:14:522024-11-10 22:36:42

Judging History

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

  • [2024-11-10 22:36:42]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:413ms
  • 内存:79788kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:48:23]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:373ms
  • 内存:79656kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-28 15:17:55]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:546ms
  • 内存:79532kb
  • [2024-10-28 15:17:17]
  • hack成功,自动添加数据
  • (/hack/1080)
  • [2024-10-28 14:29:49]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:394ms
  • 内存:79500kb
  • [2024-10-28 14:28:57]
  • hack成功,自动添加数据
  • (/hack/1079)
  • [2024-10-27 18:37:39]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:425ms
  • 内存:79336kb
  • [2024-10-27 18:36:42]
  • hack成功,自动添加数据
  • (/hack/1075)
  • [2024-10-26 17:14:52]
  • 评测
  • 测评结果:100
  • 用时:394ms
  • 内存:79220kb
  • [2024-10-26 17:14:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n,buc[800010],sa[800010],rk[800010],ht[20][800010],tmp[800010];
char s[200010],t[200010],S[800010];
void get_sa(int n,char *s)
{
	for(int i=1;i<=n;i++) buc[s[i]-'a']++;
	for(int i=1;i<=40;i++) buc[i]+=buc[i-1];
	for(int i=n;i>=1;i--) sa[buc[s[i]-'a']--]=i;
	for(int i=1;i<=n;i++) rk[sa[i]]=rk[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]);
	fill(buc,buc+41,0);
	for(int k=1;k<n;k<<=1)
	{
		int tot=0;
		for(int i=n-k+1;i<=n;i++) tmp[++tot]=i;
		for(int i=1;i<=n;i++)
			if(sa[i]>k) tmp[++tot]=sa[i]-k;
		for(int i=1;i<=n;i++) buc[rk[i]]++;
		for(int i=1;i<=n;i++) buc[i]+=buc[i-1];
		for(int i=n;i>=1;i--) sa[buc[rk[tmp[i]]]--]=tmp[i];
		fill(buc+1,buc+n+1,0);
		for(int i=1;i<=n;i++) tmp[sa[i]]=tmp[sa[i-1]]+(rk[sa[i]]!=rk[sa[i-1]] || rk[sa[i]+k]!=rk[sa[i-1]+k]);
		move(tmp+1,tmp+n+1,rk+1);
		if(rk[sa[n]]>=n) break;
	}
	for(int i=1,j=0;i<=n;i++)
	{
		while(s[i+j]==s[sa[rk[i]+1]+j]) j++;
		ht[0][rk[i]]=j;
		if(j) j--;
	}
	for(int i=1;i<=19;i++)
		for(int j=1;j+(1<<i)-1<n;j++)
			ht[i][j]=min(ht[i-1][j],ht[i-1][j+(1<<(i-1))]);
}
int lcp(int i,int j)
{
	i=rk[i];j=rk[j];
	if(i>j) swap(i,j);
	int k=__lg(j-i);
	return min(ht[k][i],ht[k][j-(1<<k)]);
}
int lcp_ss(int i,int j)
{
	if(i>n || j>n) return 0;
	return lcp(i,j);
}
int lcp_st(int i,int j)
{
	if(i>n || j>n) return 0;
	return lcp(i,j+2*(n+1));
}
int lcp_tt(int i,int j)
{
	if(i>n || j>n) return 0;
	return lcp(i+2*(n+1),j+2*(n+1));
}
int lcs_ss(int i,int j)
{
	if(i<1 || j<1) return 0;
	i=n-i+1;j=n-j+1;
	return lcp(i+n+1,j+n+1);
}
int lcs_st(int i,int j)
{
	if(i<1 || j<1) return 0;
	i=n-i+1;j=n-j+1;
	return lcp(i+n+1,j+3*(n+1));
}
int lcs_tt(int i,int j)
{
	if(i<1 || j<1) return 0;
	i=n-i+1;j=n-j+1;
	return lcp(i+3*(n+1),j+3*(n+1));
}
int main() {
	std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int m=0;
	cin>>n>>s+1>>t+1;
	for(int i=1;i<=n;i++) S[++m]=s[i];
	S[++m]='z'+1;
	for(int i=1;i<=n;i++) S[++m]=s[n-i+1];
	S[++m]='z'+2;
	for(int i=1;i<=n;i++) S[++m]=t[i];
	S[++m]='z'+3;
	for(int i=1;i<=n;i++) S[++m]=t[n-i+1];
	get_sa(m,S);
	for(int k=(n+1)/2;k>=1;k--)
	{
		bool ok=0;
		for(int i=1;i+k<=n+1;i+=k)
		{
			int j=i+k,l1=lcs_ss(i-1,j-1),l2=lcp_ss(i,j);
			if(l1+l2>=k) ok=1;
			else
			{
				int l3=lcp_st(i+l2,j+l2-1);
				if(l1+l2+l3>=k) ok=1;
			}
			if(ok) break;
			l1=lcp_tt(i,j);l2=lcs_tt(i-1,j-1);
			if(l1+l2>=k) ok=1;
			else
			{
				int l3=lcs_st(i-l2,j-l2-1);
				if(l1+l2+l3>=k) ok=1;
			}
			if(ok) break;
			l1=lcs_st(i-1,j-2);l2=lcp_st(i,j-1);
			int l3=lcs_ss(i-l1-1,j-l1-1),l4=lcp_tt(i+l2-1,j+l2-1);
			if(l1+l2+max(l3,l4)>=k) ok=1;
			if(ok) break;
		}
		if(ok)
		{
			cout<<2*k<<endl;
			return 0;
		}
	}
	cout<<0<<endl;
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 236ms
memory: 79788kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 223ms
memory: 78536kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 233ms
memory: 79068kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 413ms
memory: 78060kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 186ms
memory: 78512kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 198ms
memory: 78724kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 310ms
memory: 79328kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed