萌新求助,wa#16,20,21,22和subtask2RE,显示段错误11
查看原帖
萌新求助,wa#16,20,21,22和subtask2RE,显示段错误11
93485
AzukaVictor楼主2022/5/22 22:02
#include<bits/stdc++.h>
using namespace std;
long long n,po[20000005],hash[20000005],p=131,cnt,ans,last;
string u;
long long ch(long long l,long long r)
{
    return hash[r]-hash[l-1]*po[r-l+1];
}
long long ih(long long l,long long r,long long x)
{
    return ch(l,x-1)*po[r-x]+ch(x+1,r);
}
int main()
{
	cin>>n>>u;
	po[0]=1;
	if(n%2==0)
	{
		cout<<"NOT POSSIBLE"<<endl;
		return 0;
	}
	long long mid=(n+1)/2;
	u='0'+u;
	for(int i=1;i<=n;i++)
	{
		po[i]=po[i-1]*p;
		hash[i]=hash[i-1]*p+u[i];
	}
	for(int i=1;i<=n;i++)
	{
		/*cout<<i;
		if(i<mid)
		{
			cout<<"<"<<endl;
			cout<<ch(mid+1,n)<<" "<<ih(1,mid,i)<<endl;
		}
		if(i==mid)
		{
			cout<<"="<<endl;
			cout<<ch(mid+1,n)<<" "<<ch(1,mid-1)<<endl;
		}
		if(i>mid)
		{
			cout<<">"<<endl;
			cout<<ch(1,mid-1)<<" "<<ih(mid,n,i)<<endl;
		}*/
		if((i<mid&&ch(mid+1,n)==ih(1,mid,i))||(i==mid&&ch(mid+1,n)==ch(1,mid-1))||(i>mid&&ch(i,mid-1)==ih(mid,n,i)))
		{
			ans=i;
			long long tmp;
			if(i>mid) tmp=ch(1,mid-1);
			else tmp=ch(mid+1,n);
			if(last!=tmp)
			{
				cnt++;
				last=tmp;
			}
		}
	}
	if(cnt==1)
	{
		if(ans>mid) cout<<u.substr(1,mid-1)<<endl;
		else cout<<u.substr(mid+1)<<endl;
	}
	else if(cnt==0) cout<<"NOT POSSIBLE"<<endl;
	else cout<<"NOT UNIQUE"<<endl;
	return 0;
}
2022/5/22 22:02
加载中...