QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561345#8668. 回文路径hhiron0 19ms9224kbC++141.3kb2024-09-12 21:57:232024-09-12 21:57:24

Judging History

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

  • [2024-09-12 21:57:24]
  • 评测
  • 测评结果:0
  • 用时:19ms
  • 内存:9224kb
  • [2024-09-12 21:57:23]
  • 提交

answer

#include<bits/stdc++.h>
#define INF 0x7fffffff
#define int long long
#define ull unsigned long long
typedef long long ll;
using namespace std;
//const int MOD=547567998244353;
const int N=5e5+5;
int n,l,r,len[N];
ull po[N];
ull has1l[N],has1r[N],has2l[N],has2r[N];
string s1,s2;
ull gethash(int x,int y,ull *a){
	return (a[y]-a[x]*po[abs(y-x)]);
}
int ans=0;
void solve(){
	for(int i=1;i<=n;i++) has1l[i]=(has1l[i-1]*131+s1[i]-'a');
	for(int i=1;i<=n;i++) has2l[i]=(has2l[i-1]*131+s2[i]-'a');
	for(int i=n;i>=1;i--) has1r[i]=(has1r[i+1]*131+s1[i]-'a');
	for(int i=n;i>=1;i--) has2r[i]=(has2l[i+1]*131+s2[i]-'a');
//	cout<<s1<<endl;
	for(int i=1;i<=n;i++){
		int l=-1,r=min(n-i,i-1);
		while(r-l>1){
			int mid=(l+r)>>1;
			if(gethash(i-mid,i+mid,has1l)==gethash(i+mid,i-mid,has1r)) l=mid;
			else r=mid;
		}int poil=i-r-1,poir=i+r;
		ans=max(ans,r*2+1);
		l=0,r=min(poil-1,n-poir);
		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]*131;
	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: 0ms
memory: 5832kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

7

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 19ms
memory: 9224kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

11

result:

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

Subtask #3:

score: 0
Skipped

Dependency #1:

0%