QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#557983#8668. 回文路径zero-range0 27ms9784kbC++201.6kb2024-09-11 13:13:302024-09-11 13:13:31

Judging History

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

  • [2024-09-11 13:13:31]
  • 评测
  • 测评结果:0
  • 用时:27ms
  • 内存:9784kb
  • [2024-09-11 13:13:30]
  • 提交

answer

#include<stdio.h>
#include<algorithm>
#define M 200005
using namespace std;
typedef unsigned long long ull;
constexpr ull bs=1e9+7;
ull Ha[M],Hb[M],Pa[M],Pb[M],pw[M];
inline ull queh(ull *H,int l,int r){return H[r]-H[l-1]*pw[r-l+1];}
inline ull quep(ull *P,int l,int r){return P[l]-P[r+1]*pw[r-l+1];}
int n,res;
char a[M],b[M];
int main(){
	pw[0]=1;
	for(int i=2;i<M;++i) pw[i]=pw[i-1]*bs;
	scanf("%d%s%s",&n,a+1,b+1);
	for(int i=n;i;--i) a[i*2]=a[i],a[i*2+1]='#';
	a[1]='#';
	for(int i=n;i;--i) b[i*2+1]=b[i],b[i*2+2]='#';
	b[1]=b[2]='#';
	n=n*2+2;
	for(int i=1;i<=n;++i) Ha[i]=Ha[i-1]*bs+a[i];
	for(int i=n;i;--i) Pa[i]=Pa[i+1]*bs+a[i];
	for(int i=1;i<=n;++i) Hb[i]=Hb[i-1]*bs+b[i];
	for(int i=n;i;--i) Pb[i]=Pb[i+1]*bs+b[i];
	for(int i=1;i<=n;++i){
		int l=1,r=min(i-1,n-i),mid,ans=0;
		while(l<=r){
			mid=l+r>>1;
			if(queh(Ha,i-mid,i-1)==quep(Pa,i+1,i+mid)) l=mid+1,ans=mid;
			else r=mid-1;
		}
		int t=ans;
		res=max(res,t*2+1);
		l=1,r=min(i-t-1,n-i+1-t),ans=0;
		while(l<=r){
			mid=l+r>>1;
			if(queh(Ha,i-t-mid,i-t-1)==quep(Pb,i+t,i+t+mid-1)) l=mid+1,ans=mid;
			else r=mid-1;
		}
		res=max(res,(t+ans)*2+1);
	}
	for(int i=1;i<=n;++i){
		int l=1,r=min(i-1,n-i),mid,ans=0;
		while(l<=r){
			mid=l+r>>1;
			if(queh(Hb,i-mid,i-1)==quep(Pb,i+1,i+mid)) l=mid+1,ans=mid;
			else r=mid-1;
		}
		int t=ans;
		res=max(res,t*2+1);
		l=1,r=min(i-t,n-i-t),ans=0;
		while(l<=r){
			mid=l+r>>1;
			if(queh(Ha,i-t-mid+1,i-t)==quep(Pb,i+t+1,i+t+mid)) l=mid+1,ans=mid;
			else r=mid-1;
		}
		res=max(res,(t+ans)*2+1);
	}
	printf("%d",res/2);
}

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: 4112kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

0

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 27ms
memory: 9784kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

0

result:

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

Subtask #3:

score: 0
Skipped

Dependency #1:

0%