이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n;
const int base=31;
const int mod=1e9+7;
const int N=2e6+13;
ll f[N];
string a;
ll lt[N];
vector<int> v;
ll gethash(int l, int r){
ll val=f[r]-f[l-1]*lt[r-l+1];
val %= mod;
while(val < 0) val += mod;
return val;
}
ll getcon(int l, int r, int x, int y){
ll val=gethash(l, r) * lt[y-x+1];
val %= mod;
val += gethash(x, y);
val %= mod;
return val;
}
void scan(){
cin >> n >> a;
if(n%2==0){
cout << "NOT POSSIBLE";
exit(0);
}
a=' '+a;
lt[0]=1;
for(int i=1; i<=n; i++){
lt[i]=lt[i-1]*base%mod;
f[i]=f[i-1] * base + (a[i]-'a'+1);
f[i]%=mod;
}
}
void solve(){
for(int i=1; i<=n/2; i++){
if(getcon(1, i-1, i+1, n/2+1)==gethash(n/2+2, n)){
v.push_back(i);
}
}
if(gethash(1, n/2)==gethash(n/2+2, n)){
v.push_back(n/2+1);
}
for(int i=n/2+2; i<=n; i++){
if(gethash(1, n/2)==getcon(n/2+1, i-1, i+1, n)){
v.push_back(i);
}
}
if(v.size()==0) cout << "NOT POSSIBLE";
else if(v.size()==1){
int id=v[0];
for(int i=1; i<id; i++) cout << a[i];
for(int i=id+1; i<=n; i++) cout << a[i];
}
else cout << "NOT UNIQUE";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
scan();
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |