QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558919#8668. 回文路径randomization0 0ms0kbC++142.2kb2024-09-11 19:17:492024-09-11 19:17:50

Judging History

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

  • [2024-09-11 19:17:50]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-09-11 19:17:49]
  • 提交

answer

#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI"<<endl;}
const int N=2e5+5, B=997, mod=1e9+9;
string s, t; 
int n, ans;
char u[N], v[N]; 
struct hash{
	string s;
	int has[N], po[N], rhas[N];
	void init(string s){
		memset(has,0,sizeof has);
		memset(rhas,0,sizeof rhas); 
		po[0]=1;
		int n=s.size()-1;
		for(int i=1; i<=n; i++)po[i]=po[i-1]*B%mod;
		for(int i=1; i<=n; i++){
			has[i]=(has[i-1]+s[i])*B%mod;
//			cout<<has[i]<<' ';
		}
//		cout<<'\n';
		for(int i=n; i; i--){
			rhas[i]=(rhas[i+1]+s[i])*B%mod;
//			cout<<rhas[i]<<' ';
		}
//		cout<<'\n';
	}
	int ha(int l, int r){
		return (has[r]-has[l-1]*po[r-l+1]%mod+mod)%mod;
	}
	int rha(int l, int r){
		return (rhas[l]-rhas[r+1]*po[r-l+1]%mod+mod)%mod;
	}
}S, T;
int solve(int i, int j){
	int l=0, r=min(i-1,n-j);
	while(l<r){
		int mid=(l+r+1)>>1;
		if(S.ha(i-mid,i)==S.rha(j,j+mid))l=mid;
		else r=mid-1;
	}
	int L=i-l-1, R=j+l;
	if(L&&s[L]==t[R]){
		l=0, r=min(L-1,n-R);
		while(l<r){
			int mid=(l+r+1)>>1;
			if(S.ha(L-mid,L)==T.rha(R,R+mid))l=mid;
			else r=mid-1; 
		}
		L-=l;R+=l;
		ans=max(ans,R-L+2);
	}
	else ans=max(ans,2*l+1+(i!=j));
}
int solvet(int i, int j){
	int l=0, r=min(i-1,n-j);
	while(l<r){
		int mid=(l+r+1)>>1;
		if(T.ha(i-mid,i)==T.rha(j,j+mid))l=mid;
		else r=mid-1;
	}
	int L=i-l, R=j+l+1;
	if(R<=n&&s[L]==t[R]){
		l=0, r=min(L-1,n-R);
		while(l<r){
			int mid=(l+r+1)>>1;
			if(S.ha(L-mid,L)==T.rha(R,R+mid))l=mid;
			else r=mid-1; 
		}
		L-=l;R+=l;
		ans=max(ans,R-L+2);
	}
	else ans=max(ans,2*l+1+(i!=j));
} 
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	cin>>s>>t;
	s=' '+s;t=' '+t;
	S.init(s);T.init(t);
	for(int i=1; i<=n; i++){
		ans=max(ans,solve(i,i));
	}
	for(int i=1; i<n; i++)if(s[i]==s[i+1])ans=max(ans,solve(i,i+1));
//	cout<<ans<<endl;
	for(int i=1; i<=n; i++)ans=max(ans,solvet(i,i));
	for(int i=1; i<n; i++)if(t[i]==t[i+1])ans=max(ans,solvet(i,i+1));
	return 0;
	for(int i=1; i<=n; i++)if(s[i]==t[i]){
		int l=0, r=min(i-1,n-i);
		while(l<r){
			int mid=(l+r+1)>>1;
			if(S.ha(i-mid,i)==T.rha(i,i+mid))l=mid;
			else r=mid-1;
		}
		ans=max(ans,l*2+2);
	}
	cout<<ans<<'\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:


result:


Subtask #2:

score: 0
Runtime Error

Test #11:

score: 0
Runtime Error

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

0%