QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558963#8668. 回文路径Chendaqian0 104ms8488kbC++141.5kb2024-09-11 19:28:542024-09-11 19:28:55

Judging History

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

  • [2024-09-11 19:28:55]
  • 评测
  • 测评结果:0
  • 用时:104ms
  • 内存:8488kb
  • [2024-09-11 19:28:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const long long P=11451419198102353,bs=31;
int n;
char s[2][N];
long long pw[N];
long long sumpre[2][N],sumsuf[2][N];
int ans;
long long getpre(int co,int l,int r) {
	return (sumpre[co][r]+P-(__int128_t)sumpre[co][l-1]*pw[r-l+1]%P)%P;
}
long long getsuf(int co,int l,int r) {
	return (sumsuf[co][l]+P-(__int128_t)sumsuf[co][r+1]*pw[r-l+1]%P)%P;
}
int calc(int c1,int s1,int c2,int s2) {
	int l=1,r=min(s1,n-s2+1),res=0;
	while(l<=r) {
		int mid=(l+r)/2;
		if(getpre(c1,s1-mid+1,s1)==getsuf(c2,s2,s2+mid-1)) 
			res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}
int main() {
	cin>>n>>(s[0]+1)>>(s[1]+1);
	for(int i=1;i<=n;i++) pw[i]=pw[i-1]*bs%P;
	for(int j=0;j<2;j++) {
		for(int i=1;i<=n;i++) {
			sumpre[j][i]=(sumpre[j][i-1]*bs+s[j][i]-'a')%P;
		}
		for(int i=n;i>=1;i--) {
			sumsuf[j][i]=(sumsuf[j][i+1]*bs+s[j][i]-'a')%P;
		}
	}
	for(int i=1;i<=n;i++) {
		int p=calc(0,i,0,i),res=calc(0,i-p,1,i+p-1);
		ans=max(ans,res*2+p*2-1);
	}
	for(int i=1;i<n;i++) if(s[0][i]==s[0][i+1]) {
		int p=calc(0,i,0,i+1),res=calc(0,i-p,1,i+p);
		ans=max(ans,res*2+p*2);
	}
	for(int i=1;i<=n;i++) ans=max(ans,calc(0,i,1,i)*2);
	for(int i=1;i<=n;i++) {
		int p=calc(1,i,1,i),res=calc(0,i-p+1,1,i+p);
		ans=max(ans,res*2+p*2-1);
	}
	for(int i=1;i<n;i++) if(s[1][i]==s[1][i+1]) {
		int p=calc(1,i,1,i+1),res=calc(0,i-p+1,1,i+p+1);
		ans=max(ans,res*2+p*2);
	}
	cout<<ans<<"\n";
	return 0;
}
/*
cd PKUSC2024D1T1
g++ code.cpp -o code -std=c++14 -O2 -Wall -static
./code
*/

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

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: 104ms
memory: 8488kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

0

result:

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

Subtask #3:

score: 0
Skipped

Dependency #1:

0%