QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#686663#9522. A Simple String ProblemTx_LcyAC ✓1182ms8600kbC++142.1kb2024-10-29 15:02:542024-11-10 22:37:30

Judging History

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

  • [2024-11-10 22:37:30]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:1182ms
  • 内存:8600kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:48:55]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:100
  • 用时:1379ms
  • 内存:8476kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-29 15:02:55]
  • 评测
  • 测评结果:100
  • 用时:1243ms
  • 内存:8604kb
  • [2024-10-29 15:02:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
int const N=2e5+10;
int const B=251;
mt19937_64 rnd(random_device{}());
ull rd[127],hsh1[N],hsh2[N],bse[N];int ans,n;
string s1,s2;
inline ull query1(int l,int r){return hsh1[r]-hsh1[l-1]*bse[r-l+1];}
inline ull query2(int l,int r){return hsh2[r]-hsh2[l-1]*bse[r-l+1];}
#define mid ((l+r)>>1)
inline int lcp1(int x,int y){
	int l=1,r=min(n-x+1,n-y+1),ans=0;
	while (l<=r)
		if (query1(x,x+mid-1)==query1(y,y+mid-1)) l=(ans=mid)+1;
		else r=mid-1;
	return ans;
}
inline int lcs1(int x,int y){
	int l=1,r=min(x,y),ans=0;
	while (l<=r)
		if (query1(x-mid+1,x)==query1(y-mid+1,y)) l=(ans=mid)+1;
		else r=mid-1;
	return ans;
}
inline int lcp(int x,int y){
	int l=1,r=min(n-x+1,n-y+1),ans=0;
	while (l<=r)
		if (query1(x,x+mid-1)==query2(y,y+mid-1)) l=(ans=mid)+1;
		else r=mid-1;
	return ans;
}
inline void work(){
	rep(len,1,(n+1)/2){
		if (2*len<=ans) continue;
		for (int i=1;i+len<=n;i+=len){
			int A=i,B=i+len;
			if (lcp(A,B-1)>=len){ans=max(ans,len*2);break;}
			int sa=lcs1(A,B),sb=lcp1(A,B);
			if (sa+sb-1>=len){ans=max(ans,len*2);break;}
			else{
				int k=lcp(A+sb,B+sb-1);
				if (k+sa+sb-1>=len){ans=max(ans,len*2);break;}
			}
			{
				int sa=lcp1(A+1,B+1);
				if (sa>=len){ans=max(ans,len*2);break;}
				if (lcp(A+sa+1,B+sa)+sa>=len){ans=max(ans,len*2);break;}
			}
		}
	}
}
inline void solve(){
	cin>>n>>s1>>s2,s1=" "+s1,s2=" "+s2;
    if (n==1){
		if (s1[1]==s2[1]) cout<<"2\n";
		else cout<<"0\n";
		return;
	}
	rep(i,'a','z') rd[i]=rnd();
	rep(i,1,n)
		hsh1[i]=(hsh1[i-1]*B+rd[s1[i]]),
		hsh2[i]=(hsh2[i-1]*B+rd[s2[i]]);
	work();
	swap(s1,s2);
	for (int i=1;i<n-i+1;++i) swap(s1[i],s1[n-i+1]),swap(s2[i],s2[n-i+1]);
	rep(i,1,n)
		hsh1[i]=(hsh1[i-1]*B+rd[s1[i]]),
		hsh2[i]=(hsh2[i-1]*B+rd[s2[i]]);
	work();
	cout<<ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	bse[0]=1;
	rep(i,1,N-1) bse[i]=bse[i-1]*B;
	int t=1;
	while (t--) solve();
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 1ms
memory: 5160kb

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 1ms
memory: 6688kb

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 982ms
memory: 8444kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 482ms
memory: 8468kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 964ms
memory: 8508kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 1182ms
memory: 8428kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 521ms
memory: 8600kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 504ms
memory: 8436kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 979ms
memory: 8476kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

score: 0
Accepted
time: 1ms
memory: 6260kb

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 1ms
memory: 8304kb

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 1ms
memory: 6720kb

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

score: 0
Accepted
time: 1ms
memory: 5740kb

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

score: 0
Accepted
time: 1ms
memory: 7136kb

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

score: 0
Accepted
time: 1ms
memory: 6828kb

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

score: 0
Accepted
time: 1ms
memory: 6960kb

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

score: 0
Accepted
time: 1ms
memory: 6396kb

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed