QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#558009#8668. 回文路径DaiRuiChen0070 34ms7976kbC++171.8kb2024-09-11 13:28:062024-09-11 13:28:06

Judging History

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

  • [2024-09-11 13:28:06]
  • 评测
  • 测评结果:0
  • 用时:34ms
  • 内存:7976kb
  • [2024-09-11 13:28:06]
  • 提交

answer

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=1e5+5;
mt19937_64 rnd(time(0));
int n,ans=0;
char s[2][MAXN];
ull B,hw[26],pw[MAXN],hs[2][MAXN],rs[2][MAXN];
ull qhs(ull *h,int l,int r) { return h[r]-h[l-1]*pw[r-l+1]; }
ull qrs(ull *h,int l,int r) { return qhs(h,n-r+1,n-l+1); }
bool judge(int l,int k,int r) {
	return qhs(hs[0],l,k)*pw[r-k+1]+qhs(hs[1],k,r)==qrs(rs[1],k,r)*pw[k-l+1]+qrs(rs[0],l,k);
}
void solve() {
	for(int i=1;i<=n;++i) { //center = i
		int L=0,R=min(i-1,n-i),x=0,y=0;
		while(L<=R) {
			int t=(L+R)>>1;
			if(judge(i-t,i+t,i+t-1)) x=t,L=t+1;
			else R=t-1;
		}
		L=0,R=min(i-x-1,n-i-x+1);
		while(L<=R) {
			int t=(L+R)>>1;
			if(judge(i-x-t,i+x,i+x+t-1)) y=t,L=t+1;
			else R=t-1;
		}
		ans=max(ans,2*(x+y)+1);
	}
	for(int i=1;i<n;++i) if(s[0][i]==s[0][i+1]) { //center = i,i+1
		int L=0,R=min(i,n-i),x=0,y=0;
		while(L<=R) {
			int t=(L+R)>>1;
			if(judge(i+1-t,i+t,i+t-1)) x=t,L=t+1;
			else R=t-1;
		}
		L=0,R=min(i-x,n-i-x+1);
		while(L<=R) {
			int t=(L+R)>>1;
			if(judge(i+1-x-t,i+x,i+x+t-1)) y=t,L=t+1;
			else R=t-1;
		}
		ans=max(ans,2*(x+y));
	}
	for(int i=1;i<=n;++i) if(s[0][i]==s[1][i]) { //center = i,i
		int L=0,R=min(i,n-i+1),x=0;
		while(L<=R) {
			int t=(L+R)>>1;
			if(judge(i-x+1,i,i+x-1)) x=t,L=t+1;
			else R=t-1;
		}
		ans=max(ans,2*x);
	}
}
signed main() {
	scanf("%d%s%s",&n,s[0]+1,s[1]+1),B=rnd()|1;
	for(int c=0;c<26;++c) hw[c]=rnd()|1;
	for(int i=pw[0]=1;i<=n;++i) pw[i]=pw[i-1]*B;
	for(int o:{0,1}) {
		for(int i=1;i<=n;++i) {
			hs[o][i]=hs[o][i-1]*B+hw[s[o][i]-'a'];
			rs[o][i]=rs[o][i-1]*B+hw[s[o][n-i+1]-'a'];
		}
	}
	solve();
	swap(s[0],s[1]),swap(hs[0],rs[1]),swap(hs[1],rs[0]);
	reverse(s[0]+1,s[0]+n+1),reverse(s[1]+1,s[1]+n+1);
	solve();
	printf("%d\n",ans);
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7348kb

input:

1000
mfmlkrasfiudkzrjzyrlbpitvzfrlmjdzsurtdcmnqpsyfgobbstvplqylvciloomaljyssxtrrccywyirfvlcnchwkfwbdaoxzpfpvlruptganojnfxmnlqetptmlmoyluxvaipghtlaszoozscdmjomobyzboqqmvqjpbfjsoczhkwrlcauzjceqikbaeuiqahnldpqmohfjfzgkbfdbqnoxispkejvpncwsyelebqumapgbfdrjvuaxaphnkciwzkruijmanwslkwosgyfhwbnsthhtxrhrzlgtt...

output:

496

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 34ms
memory: 7976kb

input:

100000
ibhqhodaqcwqggmckoemulhkgbfidceskhefhsonccepfodalabaqgobpgcnaervbccadkbtsdigsoqochklocgbjjqcdhwrlacamprsoilyhiwkkjalicedhbxajrkhjgivjhnfdibkdwtexnnriegejazmohlfijbeigfmpngncokxhifjfuwuogccdfglfbxobnarmgfhgpnjjewicgfhcmfbbnjbbjjtbprnagpchcihcihfhcikeaecefdgeegtzlfdolhfieahiehdfcaflmndmcojceblf...

output:

49988

result:

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

Subtask #3:

score: 0
Skipped

Dependency #1:

0%