#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
mt19937 rando(chrono::steady_clock::now().time_since_epoch().count());
int randt(int l, int r){
return rando() % (r - l + 1) + l;
}
const int N = 2e6 + 5;
int base, mod;
inline void sadd(int& x, int y){
if ((x += y) >= mod) x -= mod;
return;
}
inline int add(int x, int y){
if ((x += y) >= mod) x -= mod;
return x;
}
inline void ssub(int& x, int y){
if ((x -= y) < 0) x += mod;
return;
}
inline int sub(int x, int y){
if ((x -= y) < 0) x += mod;
return x;
}
inline int mul(int x, int y){
return 1ll * x * y % mod;
}
inline int binpow(int x, int y){
int ans = 1;
while (y){
if (y & 1) ans = mul(ans, x);
x = mul(x, x);
y >>= 1;
}
return ans;
}
inline int inv(int x){
return binpow(x, mod - 2);
}
#define div __div__
inline int div(int x, int y){
return mul(x, binpow(y, mod - 2));
}
int fac[N], invfac[N];
void calfac(){
fac[0] = invfac[0] = 1;
For(i, 1, N){
fac[i] = mul(fac[i - 1], i);
}
invfac[N - 1] = binpow(fac[N - 1], mod - 2);
FordE(i, N - 2, 1){
invfac[i] = mul(invfac[i + 1], i + 1);
}
}
inline int C(int n, int k){
if (n < 0 or k < 0 or k > n){
return 0;
}
return mul(fac[n], mul(invfac[k], invfac[n - k]));
}
inline int P(int n, int k){
if (n < 0 or k < 0 or k > n){
return 0;
}
return mul(fac[n], invfac[n - k]);
}
bool isprime(int x){
if (x <= 1){
return 0;
}
if (x <= 3){
return 1;
}
if (x % 2 == 0 or x % 3 == 0){
return 0;
}
for (int i = 5; i * i <= x; i += 6){
if (x % i == 0 or x % (i + 2) == 0){
return 0;
}
}
return 1;
}
int n;
string s;
#define hash __hash__
int powbase[N];
int hash[N];
int calhash(int l, int r){
return sub(hash[r], mul(hash[l - 1], powbase[r - l + 1]));
}
int ans = -1, idxans = -1;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
cin >> n;
cin >> s; s = ' ' + s;
if (n % 2 == 0){
cout << "NOT POSSIBLE" << endl;
return 0;
}
base = randt(1000, 100000);
while (!isprime(base)){
base++;
}
mod = randt(500000000, 1000000000);
while (!isprime(mod)){
mod++;
}
powbase[0] = 1;
For(i, 1, N){
powbase[i] = mul(powbase[i - 1], base);
}
ForE(i, 1, n){
hash[i] = add(mul(hash[i - 1], base), s[i] - 'A' + 1);
}
int mid = n / 2 + 1;
ForE(i, 1, n){
if (i == mid){
if (calhash(1, mid - 1) == calhash(mid + 1, n)){
if (ans == -1){
ans = calhash(1, mid - 1);
idxans = i;
}
else if (ans != calhash(1, mid - 1)){
cout << "NOT UNIQUE" << endl;
return 0;
}
}
continue;
}
if (i < mid){
int val = add(mul(calhash(1, i - 1), powbase[mid - i]), calhash(i + 1, mid));
if (val == calhash(mid + 1, n)){
if (ans == -1){
ans = val;
idxans = i;
}
else if (ans != val){
cout << "NOT UNIQUE" << endl;
return 0;
}
}
}
else{
int val = add(mul(calhash(mid, i - 1), powbase[n - i]), calhash(i + 1, n));
if (val == calhash(1, mid - 1)){
if (ans == -1){
ans = val;
idxans = i;
}
else if (ans != val){
cout << "NOT UNIQUE" << endl;
return 0;
}
}
}
}
if (ans == -1){
cout << "NOT POSSIBLE" << endl;
return 0;
}
if (idxans <= mid){
ForE(i, mid + 1, n){
cout << s[i];
} cout << endl;
}
else{
ForE(i, 1, mid - 1){
cout << s[i];
} cout << endl;
}
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
8136 KB |
Output is correct |
2 |
Correct |
26 ms |
8128 KB |
Output is correct |
3 |
Correct |
27 ms |
8136 KB |
Output is correct |
4 |
Correct |
28 ms |
8132 KB |
Output is correct |
5 |
Correct |
26 ms |
8140 KB |
Output is correct |
6 |
Correct |
26 ms |
8132 KB |
Output is correct |
7 |
Correct |
27 ms |
8140 KB |
Output is correct |
8 |
Correct |
26 ms |
8140 KB |
Output is correct |
9 |
Correct |
25 ms |
8140 KB |
Output is correct |
10 |
Correct |
27 ms |
8132 KB |
Output is correct |
11 |
Correct |
26 ms |
8028 KB |
Output is correct |
12 |
Correct |
29 ms |
8140 KB |
Output is correct |
13 |
Correct |
27 ms |
8140 KB |
Output is correct |
14 |
Correct |
29 ms |
8060 KB |
Output is correct |
15 |
Correct |
27 ms |
8132 KB |
Output is correct |
16 |
Correct |
26 ms |
8140 KB |
Output is correct |
17 |
Correct |
26 ms |
8112 KB |
Output is correct |
18 |
Correct |
26 ms |
8132 KB |
Output is correct |
19 |
Correct |
28 ms |
8116 KB |
Output is correct |
20 |
Correct |
28 ms |
8072 KB |
Output is correct |
21 |
Correct |
29 ms |
8048 KB |
Output is correct |
22 |
Correct |
30 ms |
8028 KB |
Output is correct |
23 |
Correct |
26 ms |
8140 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
25 ms |
8056 KB |
Output is correct |
28 |
Correct |
26 ms |
8132 KB |
Output is correct |
29 |
Correct |
28 ms |
8032 KB |
Output is correct |
30 |
Correct |
26 ms |
8132 KB |
Output is correct |
31 |
Correct |
25 ms |
8124 KB |
Output is correct |
32 |
Correct |
25 ms |
8140 KB |
Output is correct |
33 |
Correct |
26 ms |
8080 KB |
Output is correct |
34 |
Correct |
26 ms |
8136 KB |
Output is correct |
35 |
Correct |
26 ms |
8104 KB |
Output is correct |
36 |
Correct |
27 ms |
8024 KB |
Output is correct |
37 |
Correct |
26 ms |
8144 KB |
Output is correct |
38 |
Correct |
27 ms |
8076 KB |
Output is correct |
39 |
Correct |
27 ms |
8132 KB |
Output is correct |
40 |
Correct |
26 ms |
8116 KB |
Output is correct |
41 |
Correct |
27 ms |
8132 KB |
Output is correct |
42 |
Correct |
27 ms |
8084 KB |
Output is correct |
43 |
Correct |
27 ms |
8132 KB |
Output is correct |
44 |
Correct |
26 ms |
8152 KB |
Output is correct |
45 |
Correct |
27 ms |
8064 KB |
Output is correct |
46 |
Correct |
27 ms |
8136 KB |
Output is correct |
47 |
Correct |
26 ms |
8068 KB |
Output is correct |
48 |
Correct |
26 ms |
8116 KB |
Output is correct |
49 |
Correct |
1 ms |
332 KB |
Output is correct |
50 |
Correct |
25 ms |
8072 KB |
Output is correct |
51 |
Correct |
26 ms |
8132 KB |
Output is correct |
52 |
Correct |
26 ms |
8180 KB |
Output is correct |
53 |
Correct |
27 ms |
8140 KB |
Output is correct |
54 |
Correct |
27 ms |
8140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
152 ms |
20908 KB |
Output is correct |
2 |
Correct |
158 ms |
21008 KB |
Output is correct |
3 |
Correct |
157 ms |
20924 KB |
Output is correct |
4 |
Correct |
157 ms |
20916 KB |
Output is correct |
5 |
Correct |
164 ms |
21136 KB |
Output is correct |
6 |
Correct |
6 ms |
6320 KB |
Output is correct |
7 |
Correct |
157 ms |
20944 KB |
Output is correct |
8 |
Correct |
125 ms |
18816 KB |
Output is correct |
9 |
Correct |
144 ms |
19680 KB |
Output is correct |
10 |
Correct |
151 ms |
19712 KB |
Output is correct |
11 |
Correct |
117 ms |
18040 KB |
Output is correct |
12 |
Correct |
27 ms |
8132 KB |
Output is correct |
13 |
Correct |
26 ms |
8140 KB |
Output is correct |
14 |
Correct |
25 ms |
8024 KB |
Output is correct |
15 |
Correct |
24 ms |
8136 KB |
Output is correct |
16 |
Correct |
27 ms |
8140 KB |
Output is correct |
17 |
Correct |
26 ms |
8140 KB |
Output is correct |
18 |
Correct |
26 ms |
8096 KB |
Output is correct |
19 |
Correct |
27 ms |
8140 KB |
Output is correct |
20 |
Correct |
26 ms |
8140 KB |
Output is correct |
21 |
Correct |
26 ms |
8140 KB |
Output is correct |
22 |
Correct |
26 ms |
8132 KB |
Output is correct |
23 |
Correct |
26 ms |
8132 KB |
Output is correct |
24 |
Correct |
26 ms |
8120 KB |
Output is correct |
25 |
Correct |
25 ms |
8068 KB |
Output is correct |
26 |
Correct |
26 ms |
8036 KB |
Output is correct |
27 |
Correct |
26 ms |
8144 KB |
Output is correct |
28 |
Correct |
27 ms |
8088 KB |
Output is correct |
29 |
Correct |
27 ms |
8132 KB |
Output is correct |
30 |
Correct |
27 ms |
8140 KB |
Output is correct |
31 |
Correct |
25 ms |
8084 KB |
Output is correct |
32 |
Correct |
24 ms |
8140 KB |
Output is correct |
33 |
Correct |
26 ms |
8132 KB |
Output is correct |
34 |
Correct |
26 ms |
8140 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
25 ms |
8148 KB |
Output is correct |
39 |
Correct |
26 ms |
8048 KB |
Output is correct |
40 |
Correct |
25 ms |
8136 KB |
Output is correct |
41 |
Correct |
26 ms |
8072 KB |
Output is correct |
42 |
Correct |
28 ms |
8176 KB |
Output is correct |
43 |
Correct |
26 ms |
8096 KB |
Output is correct |
44 |
Correct |
27 ms |
8132 KB |
Output is correct |
45 |
Correct |
27 ms |
8132 KB |
Output is correct |
46 |
Correct |
24 ms |
8140 KB |
Output is correct |
47 |
Correct |
26 ms |
8144 KB |
Output is correct |
48 |
Correct |
26 ms |
8132 KB |
Output is correct |
49 |
Correct |
27 ms |
8036 KB |
Output is correct |
50 |
Correct |
26 ms |
8052 KB |
Output is correct |
51 |
Correct |
26 ms |
8132 KB |
Output is correct |
52 |
Correct |
25 ms |
8064 KB |
Output is correct |
53 |
Correct |
26 ms |
8128 KB |
Output is correct |
54 |
Correct |
26 ms |
8148 KB |
Output is correct |