WA on#51#52#62#63
查看原帖
WA on#51#52#62#63
1037672
winter_star楼主2025/7/23 15:38
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
const int P = 131;
inline int read() {
	register char c=getchar();
	register int f=1,x=0;
	while(c<'0' || c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9') {
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	} return f*x;
}
inline void print2(register int x) {
	if(x<=0) return;
	print2(x/10);
	putchar((x%10)|'0');
}
inline void print(register int x) {
	if(x==0) { putchar('0'); return; }
	print2(x<0? putchar('-'),x*-1:x);
} 
inline unsigned long long fast(unsigned long long a,unsigned long long p) {
	unsigned long long res=1;
	while(p>0) {
		if(p&1) res*=a;
		a*=a;
		p>>=1;
	} return res;
}

int n;
char c[maxn];
unsigned long long h[maxn];
signed main() {
	n=read();
	for(register int i=1;i<=n;++i) scanf(" %c",&c[i]),h[i]=(int)c[i]; h[(n+1)/2]=0;
	for(register int i=n;i>(n+1)/2;--i) h[i]=h[i]*fast(P,(n-i))+h[i+1];
	for(register int i=n/2;i>0;--i) h[i]=h[i]*fast(P,((n/2)-i))+h[i+1];
	int m;
	set <unsigned long long> ans;
	ans.clear();
	for(register int k=1;k<=n;++k) {
		unsigned long long num1 = k>=(n+1)/2? h[1]:h[1]-h[k]+h[k+1]*P+c[(n+1)/2];
		unsigned long long num2 = k<=(n+1)/2? h[n/2+2]:(h[n/2+2]-h[k])/P+h[k+1]+c[(n+1)/2]*fast(P,(n-1)/2-1);
		if(num1==num2) ans.insert(num1),m=k;
	}
	if(n%2==0) { printf("NOT POSSIBLE"); return 0;}
	if(ans.size()==0) printf("NOT POSSIBLE");
	if(ans.size()==1) for(register int i=1;i<=n/2+(m<=n/2);++i) if(i!=m) putchar(c[i]);
	if(ans.size()>=2) printf("NOT UNIQUE");
	return 0;
}
```cpp
2025/7/23 15:38
加载中...