#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define INF ((ll)(1e9) + 7)
//#define INF (998244353ll)
#define N (int)(2e6 + 5)
using namespace std;
#define int ll
#define lsb(x) (x & (-x))
const int P = 31;
int n, k, g;
int po[N];
int h[N];
int f(int l, int r){
if(r < l)return 0;
if(l == 0)return h[r];
return (h[r] - (h[l - 1] * po[r - l + 1]) % INF + INF) % INF;
}
int f2(int l, int r, int del){
int h1 = f(l, del - 1);
int h2 = f(del + 1, r);
if(del == r){
return h1;
}
return ((h1 * P) + h2) % INF;
}
void solve(){
cin >> n;
string s;
cin >> s;
po[0] = 1;
h[0] = (s[0] - 'A') + 1;
for(int i=1; i<n; i++){
h[i] = (h[i - 1] * P + ((s[i] - 'A') + 1)) % INF;
po[i] = po[i - 1] * P % INF;
}
int ind = -1;
set<int> ss;
for(int i=0; i<n; i++){
int sts = 0, ends = 0;
if(i >= n/2){
sts = f(0, n/2 - 1);
}
else{
sts = f2(0, n/2, i);
}
if(i <= n/2){
ends = f(n/2 + 1, n - 1);
}
else{
ends = f2(n/2, n - 1, i);
}
if(sts == ends){
ss.insert(sts);
ind = i;
}
}
int ans = ss.size();
if(ans == 0){
cout << "NOT POSSIBLE";
}
else if(ans == 1){
string res;
for(int i=0; i<n && int(res.size()) < n/2; i++){
if(i != ind)res += s[i];
}
cout << res;
}
else{
cout << "NOT UNIQUE";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
//cin>>T;
//pre();
for(int i=1; i<=T; i++){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
35564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
