QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#851405#8701. BorderANIG0 13ms56568kbC++141.7kb2025-01-10 18:35:492025-01-10 18:35:49

Judging History

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

  • [2025-01-10 18:35:49]
  • 评测
  • 测评结果:0
  • 用时:13ms
  • 内存:56568kb
  • [2025-01-10 18:35:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e6+5,mods=1e9+9;
string s,t;
int n,p1[N],p2[N],f1[N],f2[N],h[N],pw[N];
set<int>jl;
vector<int>g[N];
int rdc(ll x){
	return (x%mods+mods)%mods;
}
int gets(int l,int r){
	return rdc(h[r]-1ll*h[l-1]*pw[r-l+1]%mods);
}
int gets(int l,int r,int k,int b){
	if(k<l||k>r)return gets(l,r);
	return rdc(1ll*gets(l,k-1)*pw[r-k+1]%mods+1ll*b*pw[r-k]%mods+gets(k+1,r));
}
signed main(){
	cin>>s>>t;
	jl.insert(0);
	n=s.size();
	for(int i=1;i<=n;i++)p1[i]=s[i-1]-'a'+1,p2[i]=t[i-1]-'a'+1;
	pw[0]=1;
	for(int i=1;i<=n;i++)h[i]=(1ll*h[i-1]*131+p1[i])%mods,pw[i]=1ll*pw[i-1]*131%mods;
	f1[1]=n;
	while(p1[f1[2]+1]==p1[f1[2]+2])f1[2]++;
	for(int i=3,k=2;i<=n;i++){
		int to=i-k+1;
		if(i+f1[to]<k+f1[k])f1[i]=f1[to];
		else{
			f1[i]=max(0,k+f1[k]-i);
			while(p1[f1[i]+1]==p1[i+f1[i]])f1[i]++;
			k=i;
		}
	}
	reverse(p1+1,p1+n+1);
	f2[1]=n;
	while(p1[f2[2]+1]==p1[f2[2]+2])f2[2]++;
	for(int i=3,k=2;i<=n;i++){
		int to=i-k+1;
		if(i+f2[to]<k+f2[k])f2[i]=f2[to];
		else{
			f2[i]=max(0,k+f2[k]-i);
			while(p1[f2[i]+1]==p1[i+f2[i]])f2[i]++;
			k=i;
		}
	}
	reverse(p1+1,p1+n+1);
	reverse(f2+1,f2+n+1);
	for(int i=1;i<=n;i++){
		if(f1[n-i+1]==i)jl.insert(i);
		else{
			if(2*i<=n){
				if(f1[n-i+1]+f2[i]+1==i){
					g[f1[n-i+1]+1].push_back(i);
					g[n-f2[i]].push_back(i);
				}
			}else{
				if(gets(f1[n-i+1]+2,i-f2[i]-1)==gets(n-i+f1[n-i+1]+2,n-f2[i]-1)){
					g[n-i+f1[n-i+1]+1].push_back(i);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		int res=0;
		for(int c=1;c<=n;c++){
			if(gets(1,c,i,p2[i])==gets(n-c+1,n,i,p2[i]))res=max(res,c);
		}
		cout<<res<<"\n";
	}
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 13ms
memory: 56568kb

input:

cbaababaabacbaababaabacbaabacbaababaabacbaaba
dabbababbabaabbafabbgbaabfebaabzababbayaabcac

output:

45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45
45

result:

wrong answer 1st numbers differ - expected: '0', found: '45'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%