QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#689168#9522. A Simple String ProblemyhdddAC ✓1114ms9088kbC++143.0kb2024-10-30 15:38:232024-11-10 22:37:47

Judging History

This is the latest submission verdict.

  • [2024-11-10 22:37:47]
  • 自动重测本题所有获得100分的提交记录
  • Verdict: AC
  • Time: 1114ms
  • Memory: 9088kb
  • [2024-11-10 22:36:11]
  • hack成功,自动添加数据
  • (/hack/1163)
  • [2024-11-06 21:49:15]
  • 自动重测本题所有获得100分的提交记录
  • Verdict: 100
  • Time: 1142ms
  • Memory: 9092kb
  • [2024-11-06 21:48:00]
  • hack成功,自动添加数据
  • (/hack/1142)
  • [2024-10-30 15:38:24]
  • Judged
  • Verdict: 100
  • Time: 1131ms
  • Memory: 9024kb
  • [2024-10-30 15:38:23]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define db double
using namespace std;
const int maxn=200010;
const int inf=1e18;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
	return x*f;
}
bool Mbe;

int n,ans;
char s[maxn],t[maxn];
int val[26],bas,pw[maxn];
int hsh1[maxn],hsh2[maxn];
mt19937 rnd(time(0));
int que1(int l,int r){
	if(l<=0||l>r||r>n)return rnd();
	return (hsh1[r]+mod-hsh1[l-1]*pw[r-l+1]%mod)%mod;}
int que2(int l,int r){
	if(l<=0||l>r||r>n)return rnd();
	return (hsh2[r]+mod-hsh2[l-1]*pw[r-l+1]%mod)%mod;}
int lcp1(int u,int v){
	if(s[u]!=s[v])return 0;
	int l=1,r=n-max(u,v)+1,res=0;
	while(l<=r){
		int mid=l+r>>1;
		if(que1(u,u+mid-1)==que1(v,v+mid-1))l=mid+1,res=mid;
		else r=mid-1;
	}
	return res;
}
int lcp12(int u,int v){
	if(s[u]!=t[v])return 0;
	int l=1,r=n-max(u,v)+1,res=0;
	while(l<=r){
		int mid=l+r>>1;
		if(que1(u,u+mid-1)==que2(v,v+mid-1))l=mid+1,res=mid;
		else r=mid-1;
	}
	return res;
}
int lcs1(int u,int v){
	if(s[u]!=s[v])return 0;
	int l=1,r=min(u,v),res=0;
	while(l<=r){
		int mid=l+r>>1;
		if(que1(u-mid+1,u)==que1(v-mid+1,v))l=mid+1,res=mid;
		else r=mid-1;
	}
	return res;
}
int lcs12(int u,int v){
	if(s[u]!=t[v])return 0;
	int l=1,r=min(u,v),res=0;
	while(l<=r){
		int mid=l+r>>1;
		if(que1(u-mid+1,u)==que2(v-mid+1,v))l=mid+1,res=mid;
		else r=mid-1;
	}
	return res;
}
void sovle(){
	for(int i=1;i<=n;i++)hsh1[i]=(hsh1[i-1]*bas+val[s[i]-'a'])%mod;
	for(int i=1;i<=n;i++)hsh2[i]=(hsh2[i-1]*bas+val[t[i]-'a'])%mod;
	// cout<<que1(1,1)<<" "<<que2(1,1)<<"\n";
	for(int len=(n+1)/2;len;len--){
		if(len*2<=ans)break;
		for(int i=1;i+len-1<=n;i+=len){
			int j=i+len;
			// cout<<i<<" "<<j<<"\n";
			if(lcp12(i,j-1)>=len){ans=max(ans,len<<1);break;}
			int bk=lcp1(i,j),fr=lcs1(i,j);
			// cout<<i<<" "<<j<<" "<<bk<<" "<<fr<<"\n";
			if(fr+bk-1>=len){ans=max(ans,len<<1);break;}
			if(lcp12(i+bk,j+bk-1)+bk+fr-1>=len){ans=max(ans,len<<1);break;}
			bk=lcp12(i,j-1),fr=lcs12(i,j-1);
			int l=len-(fr+bk-1);
			// cout<<i<<" "<<j-1<<" "<<s[i]<<" "<<t[j-1]<<" "<<bk<<" "<<fr<<"\n";
			// cout<<i+bk<<" "<<j-1-fr+1<<" "<<i-fr-l+1<<" "<<i-fr<<"\n";
			if(que1(i+bk,j-1-fr+1)==que1(i-fr-l+1,i-fr)){ans=max(ans,len<<1);break;}
		}
	}
}
void work(){
	n=read();scanf("%s%s",s+1,t+1);
	if(n==1){
		printf("%lld\n",(s[1]==t[1])*2);
		return ;
	}
	bas=rnd()%mod;for(int i=0;i<26;i++)val[i]=rnd()%mod;
	pw[0]=1;for(int i=1;i<=n;i++)pw[i]=pw[i-1]*bas%mod;
	sovle();
	swap(s,t),reverse(s+1,s+n+1),reverse(t+1,t+n+1);
	sovle();
	printf("%lld\n",ans);
}

// \
444

bool Med;
int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
//	cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
	
	T=1;
	while(T--)work();
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 6384kb

input:

5
abcab
acabc

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6
babbaa
babaaa

output:

6

result:

ok single line: '6'

Test #3:

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

input:

2
ne
fu

output:

0

result:

ok single line: '0'

Test #4:

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

input:

6
baabba
baabab

output:

4

result:

ok single line: '4'

Test #5:

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

input:

6
aaabba
aabbba

output:

2

result:

ok single line: '2'

Test #6:

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

input:

6
abaabb
bbbaba

output:

4

result:

ok single line: '4'

Test #7:

score: 0
Accepted
time: 116ms
memory: 9088kb

input:

200000
wvblpxtatzytphgshchrevqqpnbljlorfoqubygysrivtemegmgrepemnlcbfqalpqqpvuockkbbvjnouhcerxqibevbipsxuscjejlcdtxoxipwrfrjwnriubvdgdgzlydwwiueovtrzljqxwfegejukncmahbcbsraxboukdesrzbwfvbpxpdntauidrybccwaocfwntohdkhxkfqhnoccyaylvvfebckmslrthubxrxvjoqcredanofbmgtsnswgszwhjckqeiddzvpnxphjkrwlsbthdvhzgn...

output:

200000

result:

ok single line: '200000'

Test #8:

score: 0
Accepted
time: 7ms
memory: 8948kb

input:

199999
klwumjcvuqinrkcsyvgfixhwvrwbmazkclblcnlpyxtlmmpkllkpukmxaurpukvgibcsuigcoqnnreivrlrwfdqofqcwubpolnnxcansyaevdjvnhnzvjeoejktaodusltockhtuqrohqfsrezdzurowghmcateztzlltkzlqynxpgbqsvgqtpukmfgdxopynqaegmjxvjixyzjrhbgahxwkswgpanhrdgpyvtvcpsihdvmtixfskuiprfqrfknohthfblkzlrcyqewdycoljgwrhjkmoxqmtogmg...

output:

200000

result:

ok single line: '200000'

Test #9:

score: 0
Accepted
time: 111ms
memory: 9020kb

input:

200000
yagcbqaxecsgdijvsdsqlemrrhyyuysvlbkkgultlmrapzokempkzmyyvgabgtqifgqhwyudzbkbjncsuixvyffpvtuczjakknocyskvqaohfvxomjhzirykpdwisgkmyomejaxbzamrnfcxjwjouskvjfuriurzknmhfvpvbdqunfckdmxhndvffhuybezncgohzwxvwfscltbhwvgvbrrejtuixsdwetkdxlogepphsvhyzybisqixsledftgegzbslkqsalhoifysrxsbjxvpojjxkqqoumlkj...

output:

114514

result:

ok single line: '114514'

Test #10:

score: 0
Accepted
time: 1114ms
memory: 8940kb

input:

200000
cbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbabcbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcbabcacbabcbacabcacbacabcbabcacbacabcacbabcbacabcacbacabcbabcacbabcbaca...

output:

0

result:

ok single line: '0'

Test #11:

score: 0
Accepted
time: 30ms
memory: 8944kb

input:

200000
bbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbaba...

output:

150050

result:

ok single line: '150050'

Test #12:

score: 0
Accepted
time: 53ms
memory: 8896kb

input:

200000
babababbaaaaaaabbbaaabbbbaaabbaaaabbaababbabbbbbababbbabbbaaabaaabaabbaabbaabbabbaaaaaababbbbbbaaaabaababbabaaabbbbbbabaaaabaaabaaaababaaabbbbbbaaabaabaaabbabbbabbbabaaaabbbbbbabbaabbaaaaaaaaabababbabbbbbaabaabaaabababbaabbbbbbabbaaaaababaabbaaaabbbbaaababbabbaabaabaabaaabbabaaaaabbabababbbaa...

output:

131072

result:

ok single line: '131072'

Test #13:

score: 0
Accepted
time: 221ms
memory: 9084kb

input:

200000
rhqtphowacdrsxqisrqjhcsmxvwqtbmsvawxxxujgibnowkeyzhnjihsvsuklueukevgvlfqnrhalhglqlknerjwzizhxxszwjtnroubsjdhbnekbolwxaigyeypumuncdhmqqeljoyewehkhsqfoirchdnwazypwtefdyvtockpluejsftmffgbgdcotjnnkimawpflzwurdwrmpeudobzhpoyktufkgyvxpbfhuzswkrmnfzultfxdefoffvrfmuoufylyfvexnxgwgqfbiqvwpyenoqxncisuz...

output:

8

result:

ok single line: '8'

Test #14:

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

input:

10
aaabaabaaa
aabbbaaaba

output:

6

result:

ok single line: '6'

Test #15:

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

input:

17
ababbbaabbbaaaaba
abbabbbbbaabaabba

output:

10

result:

ok single line: '10'

Test #16:

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

input:

22
aaabbbaaaababbabbbbbbb
bbaabbbbbaaabbbabaaaaa

output:

8

result:

ok single line: '8'

Test #17:

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

input:

15
abaabaaaaabbbab
abbbabbbabababa

output:

8

result:

ok single line: '8'

Test #18:

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

input:

5
aabba
baaba

output:

6

result:

ok single line: '6'

Test #19:

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

input:

1
a
a

output:

2

result:

ok single line: '2'

Test #20:

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

input:

100
baabaaaabaabaabaaabaabbbabbbbbaababbabbbabbbbababaaabbabbaaaabbbaaabaabbbaaaaaababaababbbbbaaabbaabb
abbbbbbbbaaaaababbabbabbbbbaaaabbabbbaaaaabababbbabbababbbabbaabbabbabbbaaababbabbabbabbbabbbababaaa

output:

20

result:

ok single line: '20'

Test #21:

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

input:

32
babbbbbabbababaabbbaaaaabbaababa
abbbaaababaabababbaaabaaabbaaaab

output:

18

result:

ok single line: '18'

Extra Test:

score: 0
Extra Test Passed