QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561295#8668. 回文路径hhiron0 44ms16112kbC++141.3kb2024-09-12 21:41:252024-09-12 21:41:25

Judging History

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

  • [2024-09-12 21:41:25]
  • 评测
  • 测评结果:0
  • 用时:44ms
  • 内存:16112kb
  • [2024-09-12 21:41:25]
  • 提交

answer

#include<bits/stdc++.h>
#define INF 0x7fffffff
#define int long long
typedef long long ll;
using namespace std;
const int MOD=998244353;
const int N=5e5+5;
int n,l,r,len[N],po[N];
int has1l[N],has1r[N],has2l[N],has2r[N];
string s1,s2;
int gethash(int x,int y,int *a){
	return (a[y]-a[x]*po[y-x]%MOD+MOD)%MOD;
}
int ans=0;
void solve(){
	for(int i=1;i<=n;i++) has1l[i]=(has1l[i-1]*31%MOD+s1[i]-'a')%MOD;
	for(int i=1;i<=n;i++) has2l[i]=(has2l[i-1]*31%MOD+s2[i]-'a')%MOD;
	for(int i=n;i>=1;i--) has1r[i]=(has1r[i+1]*31%MOD+s1[i]-'a')%MOD;
	for(int i=n;i>=1;i--) has2r[i]=(has2l[i+1]*31%MOD+s2[i]-'a')%MOD;
//	cout<<s1<<endl;
	for(int i=1;i<=n;i++){
		int l=-1,r=min(n-i,i);
		while(r-l>1){
			int mid=(l+r)>>1;
			if(gethash(i-mid,i+mid,has1l)==gethash(i+mid,i-mid,has1r)) r=mid;
			else l=mid;
		}int poil=i-r-1,poir=i+r;
		l=0,r=min(poil,n-poir);
		ans=max(ans,r*2+1);
		if(s1[poil]!=s2[poir]) continue;
//		while(r-l>1){
//			int mid=(l+r)>>1;
//			if(gethash(mid))
//		}
	}
}
signed main(){
	cin>>n>>s1>>s2;
	s1=" "+s1; s2=" "+s2;
	po[0]=1;
	for(int i=1;i<=n;i++) po[i]=po[i-1]*31%MOD;
	solve();
	swap(s1,s2);
	for(int i=1;i<=n/2;i++) swap(s1[i],s1[n-i+1]);
	for(int i=1;i<=n/2;i++) swap(s2[i],s2[n-i+1]);
	solve();
	printf("%lld",ans);
	return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5804kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

5

result:

wrong answer 1st lines differ - expected: '6', found: '5'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 44ms
memory: 16112kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

5

result:

wrong answer 1st lines differ - expected: '9', found: '5'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%