이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=2e6+10, P=313, mod=1e9+696969;
int n;
ll hasz[MAX], pot[MAX];
string s;
ll fh(int a, int b){
return ((hasz[b]-(hasz[a-1]*pot[b-a+1])%mod)+mod)%mod;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
pot[0]=1;
for(int i=1; i<=MAX-5; i++)
pot[i]=(pot[i-1]*P)%mod;
cin>>n>>s;
if(n%2==0){
cout<<"NOT POSSIBLE\n";
return 0;
}
s='%'+s;
for(int i=1; i<=n; i++)
hasz[i]=((hasz[i-1]*P)%mod+(s[i]-'A'))%mod;
int ile=0, wyn=0;
ll last=0;
for(int i=1; i<=n; i++){
if(i==n/2+1 && fh(1, n/2)==fh(n/2+2, n)){
if(last!=-1 && fh(n/2+2, n)!=last){
cout<<"NOT UNIQUE\n";
return 0;
}
ile++, wyn=i, last=fh(n/2+2, n);
}
if(i<n/2+1){
ll l=fh(1, i-1), p=fh(i+1, n/2+1);
ll caly=((l*pot[n/2+1-i-1+1])%mod+p)%mod;
if(caly==fh(n/2+2, n)){
if(last!=-1 && caly!=last){
cout<<"NOT UNIQUE\n";
return 0;
}
wyn=i, ile++, last=caly;
}
}
if(i>n/2+1){
ll l=fh(n/2+1, i-1), p=fh(i+1, n);
ll caly=((l*pot[max(0, n-i-1+1)])%mod+p)%mod;
if(caly==fh(1, n/2)){
if(last!=-1 && caly!=last){
cout<<"NOT UNIQUE\n";
return 0;
}
wyn=i, ile++, last=caly;
}
}
}
if(!ile)
cout<<"NOT POSSIBLE\n";
else{
int xd=0;
for(int i=1; i<=n; i++){
if(i!=wyn){
cout<<s[i];
xd++;
}
if(xd==n/2)
break;
}
cout<<"\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |