#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 9;
const int C = 2017;
ll modpow(ll a, ll b)
{
if(b<0) b+=(MOD-1);
ll r= 1;
while(b)
{
if(b&1) r = (r*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return r;
}
ll inv(ll x)
{
return modpow(x, MOD - 2);
}
ll invC;
ll dp[2000001];
ll hsh(int l, int r)
{
if(r<l) return 0;
r++; l++;
return ((dp[r] - dp[l-1])%MOD+MOD)%MOD;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
//freopen("friend.in", "r", stdin);
invC = inv(C);
int n; string s;
cin >> n >> s;
if(n%2==0)
{
cout << "NOT POSSIBLE";
return 0;
}
int l = n/2;
vi pos;
//string a = s.substr(0, l);
//string b = s.substr(l, l);
//if(a == b) pos = n - 1;
bool started = false;
bool flag = true; char theletter = '$';
ll CMOD = modpow(C,l+1);
for(int i = 1; i <= n; i++)
{
dp[i] = (dp[i-1] + ll(s[i-1]-'A'+1)*modpow(C, n - i))%MOD;
}
for(int i = 0; i < n; i++) //it's placed at pos i
{
if(started)
{
if(s[i] != theletter) flag = false;
}
if(i < l)
{
ll h1 = hsh(0,i-1);
ll h2 = hsh(i+1,l);
h2 = (h2*C)%MOD;
h1 += h2;
h1%=MOD;
if(h1 == (hsh(l+1,n-1)*CMOD)%MOD)
{
pos.pb(i);
if(!flag)
{
cout << "NOT UNIQUE";
return 0;
}
if(!started)
{
started = true;
theletter = s[i];
}
}
}
if(i == l)
{
if(hsh(0,l-1)==(hsh(l+1,n-1)*CMOD)%MOD)
{
pos.pb(i);
if(!flag)
{
cout << "NOT UNIQUE";
return 0;
}
if(!started)
{
started = true;
theletter = s[i];
}
}
}
if(i > l)
{
ll h1 = hsh(l,i-1);
ll h2 = hsh(i+1,n-1);
h1=(h1*invC)%MOD;
h1=(h1+h2)%MOD;
if(hsh(0,l-1)==(h1*CMOD)%MOD)
{
pos.pb(i);
if(!flag)
{
cout << "NOT UNIQUE";
return 0;
}
if(!started)
{
started = true;
theletter = s[i];
}
}
}
}
if(pos.empty())
{
cout << "NOT POSSIBLE"; return 0;
}
/*
char commonletter = s[pos[0]];
for(int i = 0; i < pos.size(); i++)
{
if(s[pos[i]] != commonletter)
{
cout << "NOT POSSIBLE"; return 0;
}
}
*/
int cnt = 0;
for(int i = 0; i < pos[0]; i++)
{
if(cnt >= l) break;
cout << s[i];
cnt++;
}
for(int i = pos[0] + 1; i < n; i++)
{
if(cnt >= l) break;
cout << s[i];
cnt++;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
17804 KB |
Output is correct |
2 |
Correct |
0 ms |
17804 KB |
Output is correct |
3 |
Correct |
0 ms |
17804 KB |
Output is correct |
4 |
Correct |
0 ms |
17804 KB |
Output is correct |
5 |
Correct |
0 ms |
17804 KB |
Output is correct |
6 |
Correct |
0 ms |
17804 KB |
Output is correct |
7 |
Correct |
0 ms |
17804 KB |
Output is correct |
8 |
Correct |
0 ms |
17804 KB |
Output is correct |
9 |
Correct |
0 ms |
17804 KB |
Output is correct |
10 |
Correct |
0 ms |
17804 KB |
Output is correct |
11 |
Correct |
0 ms |
17804 KB |
Output is correct |
12 |
Correct |
0 ms |
17804 KB |
Output is correct |
13 |
Correct |
0 ms |
17804 KB |
Output is correct |
14 |
Correct |
0 ms |
17804 KB |
Output is correct |
15 |
Correct |
0 ms |
17804 KB |
Output is correct |
16 |
Correct |
0 ms |
17804 KB |
Output is correct |
17 |
Correct |
0 ms |
17804 KB |
Output is correct |
18 |
Correct |
0 ms |
17804 KB |
Output is correct |
19 |
Correct |
0 ms |
17804 KB |
Output is correct |
20 |
Correct |
0 ms |
17804 KB |
Output is correct |
21 |
Correct |
0 ms |
17804 KB |
Output is correct |
22 |
Correct |
0 ms |
17804 KB |
Output is correct |
23 |
Correct |
0 ms |
17804 KB |
Output is correct |
24 |
Correct |
0 ms |
17804 KB |
Output is correct |
25 |
Correct |
0 ms |
17804 KB |
Output is correct |
26 |
Correct |
0 ms |
17804 KB |
Output is correct |
27 |
Correct |
0 ms |
17804 KB |
Output is correct |
28 |
Correct |
0 ms |
17804 KB |
Output is correct |
29 |
Correct |
0 ms |
17804 KB |
Output is correct |
30 |
Correct |
0 ms |
17804 KB |
Output is correct |
31 |
Correct |
0 ms |
17804 KB |
Output is correct |
32 |
Correct |
0 ms |
17804 KB |
Output is correct |
33 |
Correct |
0 ms |
17804 KB |
Output is correct |
34 |
Correct |
0 ms |
17804 KB |
Output is correct |
35 |
Correct |
0 ms |
17804 KB |
Output is correct |
36 |
Correct |
0 ms |
17804 KB |
Output is correct |
37 |
Correct |
0 ms |
17804 KB |
Output is correct |
38 |
Correct |
0 ms |
17804 KB |
Output is correct |
39 |
Correct |
0 ms |
17804 KB |
Output is correct |
40 |
Correct |
0 ms |
17804 KB |
Output is correct |
41 |
Correct |
0 ms |
17804 KB |
Output is correct |
42 |
Correct |
0 ms |
17804 KB |
Output is correct |
43 |
Correct |
0 ms |
17804 KB |
Output is correct |
44 |
Correct |
0 ms |
17804 KB |
Output is correct |
45 |
Correct |
0 ms |
17804 KB |
Output is correct |
46 |
Correct |
0 ms |
17804 KB |
Output is correct |
47 |
Correct |
0 ms |
17804 KB |
Output is correct |
48 |
Correct |
0 ms |
17804 KB |
Output is correct |
49 |
Correct |
0 ms |
17804 KB |
Output is correct |
50 |
Correct |
0 ms |
17804 KB |
Output is correct |
51 |
Correct |
0 ms |
17804 KB |
Output is correct |
52 |
Correct |
0 ms |
17804 KB |
Output is correct |
53 |
Correct |
0 ms |
17804 KB |
Output is correct |
54 |
Correct |
0 ms |
17804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
356 ms |
20908 KB |
Execution killed because of forbidden syscall writev (20) |
2 |
Halted |
0 ms |
0 KB |
- |