#include <bits/stdc++.h>
using namespace std;
void out() { printf("NOT POSSIBLE\n"); exit(0); }
const int N = 2000005;
const int md = 1e9 + 123;
const int BASE = 27;
string s;
int n;
int ans, pos;
int H[N];
int pw[N];
vector < pair<int,int> > A;
int get(int l, int r) {
if (l > r) return 0;
int res = (H[r] - (1LL * H[l-1] * pw[r - l + 1] % md)) % md;
if (res < 0) res += md; return res;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> s; s = ' ' + s;
if (n % 2 == 0) out();
pw[0] = 1; for (int i = 1; i < N; ++i) pw[i] = 1LL * pw[i-1] * BASE % md;
for (int i = 1; i <= n; ++i) H[i] = (1LL * H[i-1] * BASE + s[i] - 'A') % md;
int sz = n / 2;
for (int i = 1; i <= n; ++i) {
int H0 = 0, H1 = 0;
if (i <= sz + 1) {
H0 = (1LL * get(1, i - 1) * pw[sz - i + 1] % md + get(i + 1, sz + 1)) % md;
H1 = get(sz + 2, n);
} else {
H0 = get(1, sz);
H1 = (1LL * get(sz + 1, i - 1) * pw[sz * 2 - i + 1] % md + get(i + 1, n)) % md;
}
if (H0 == H1) A.push_back(make_pair(H0, i));
}
sort(A.begin(), A.end());
if (A.empty()) out();
else {
for (int i = 0; i < (int)A.size(); ++i) if (A[i].first != A[0].first) return printf("NOT UNIQUE\n"), 0;
int pos = A[0].second;
if (pos <= sz + 1) for (int i = sz + 2; i <= n; ++i) printf("%c", s[i]);
else for (int i = 1; i <= sz; ++i) printf("%c", s[i]);
printf("\n");
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
17804 KB |
Output is correct |
2 |
Correct |
13 ms |
17804 KB |
Output is correct |
3 |
Correct |
13 ms |
17804 KB |
Output is correct |
4 |
Correct |
16 ms |
17804 KB |
Output is correct |
5 |
Correct |
13 ms |
17804 KB |
Output is correct |
6 |
Correct |
13 ms |
17804 KB |
Output is correct |
7 |
Correct |
16 ms |
17804 KB |
Output is correct |
8 |
Correct |
6 ms |
17804 KB |
Output is correct |
9 |
Correct |
16 ms |
17804 KB |
Output is correct |
10 |
Correct |
16 ms |
17804 KB |
Output is correct |
11 |
Correct |
13 ms |
17804 KB |
Output is correct |
12 |
Correct |
16 ms |
17804 KB |
Output is correct |
13 |
Correct |
16 ms |
17804 KB |
Output is correct |
14 |
Correct |
9 ms |
17804 KB |
Output is correct |
15 |
Correct |
13 ms |
17804 KB |
Output is correct |
16 |
Correct |
13 ms |
17804 KB |
Output is correct |
17 |
Correct |
16 ms |
17804 KB |
Output is correct |
18 |
Correct |
13 ms |
17804 KB |
Output is correct |
19 |
Correct |
16 ms |
17804 KB |
Output is correct |
20 |
Correct |
16 ms |
17804 KB |
Output is correct |
21 |
Correct |
9 ms |
17804 KB |
Output is correct |
22 |
Correct |
16 ms |
17804 KB |
Output is correct |
23 |
Correct |
13 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 |
13 ms |
17804 KB |
Output is correct |
28 |
Correct |
9 ms |
17804 KB |
Output is correct |
29 |
Correct |
6 ms |
17804 KB |
Output is correct |
30 |
Correct |
13 ms |
17804 KB |
Output is correct |
31 |
Correct |
9 ms |
17804 KB |
Output is correct |
32 |
Correct |
6 ms |
17804 KB |
Output is correct |
33 |
Correct |
16 ms |
17804 KB |
Output is correct |
34 |
Correct |
13 ms |
17804 KB |
Output is correct |
35 |
Correct |
13 ms |
17804 KB |
Output is correct |
36 |
Correct |
9 ms |
17804 KB |
Output is correct |
37 |
Correct |
6 ms |
17804 KB |
Output is correct |
38 |
Correct |
13 ms |
17804 KB |
Output is correct |
39 |
Correct |
16 ms |
17804 KB |
Output is correct |
40 |
Correct |
9 ms |
17804 KB |
Output is correct |
41 |
Correct |
16 ms |
17804 KB |
Output is correct |
42 |
Correct |
13 ms |
17804 KB |
Output is correct |
43 |
Correct |
9 ms |
17804 KB |
Output is correct |
44 |
Correct |
13 ms |
17804 KB |
Output is correct |
45 |
Correct |
16 ms |
17804 KB |
Output is correct |
46 |
Correct |
13 ms |
17804 KB |
Output is correct |
47 |
Correct |
9 ms |
17804 KB |
Output is correct |
48 |
Correct |
9 ms |
17804 KB |
Output is correct |
49 |
Correct |
0 ms |
17804 KB |
Output is correct |
50 |
Correct |
13 ms |
17804 KB |
Output is correct |
51 |
Correct |
16 ms |
17804 KB |
Output is correct |
52 |
Correct |
13 ms |
17804 KB |
Output is correct |
53 |
Correct |
16 ms |
17804 KB |
Output is correct |
54 |
Correct |
13 ms |
17804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
149 ms |
21840 KB |
Output is correct |
2 |
Correct |
136 ms |
21840 KB |
Output is correct |
3 |
Correct |
156 ms |
21840 KB |
Output is correct |
4 |
Correct |
143 ms |
21840 KB |
Output is correct |
5 |
Correct |
143 ms |
21840 KB |
Output is correct |
6 |
Correct |
0 ms |
21840 KB |
Output is correct |
7 |
Correct |
239 ms |
46424 KB |
Output is correct |
8 |
Correct |
89 ms |
21644 KB |
Output is correct |
9 |
Correct |
126 ms |
21644 KB |
Output is correct |
10 |
Correct |
129 ms |
21644 KB |
Output is correct |
11 |
Correct |
73 ms |
21512 KB |
Output is correct |
12 |
Correct |
6 ms |
17804 KB |
Output is correct |
13 |
Correct |
13 ms |
17804 KB |
Output is correct |
14 |
Correct |
16 ms |
17804 KB |
Output is correct |
15 |
Correct |
6 ms |
17804 KB |
Output is correct |
16 |
Correct |
13 ms |
17804 KB |
Output is correct |
17 |
Correct |
13 ms |
17804 KB |
Output is correct |
18 |
Correct |
9 ms |
17804 KB |
Output is correct |
19 |
Correct |
16 ms |
17804 KB |
Output is correct |
20 |
Correct |
16 ms |
17804 KB |
Output is correct |
21 |
Correct |
13 ms |
17804 KB |
Output is correct |
22 |
Correct |
16 ms |
17804 KB |
Output is correct |
23 |
Correct |
13 ms |
17804 KB |
Output is correct |
24 |
Correct |
16 ms |
17804 KB |
Output is correct |
25 |
Correct |
16 ms |
17804 KB |
Output is correct |
26 |
Correct |
9 ms |
17804 KB |
Output is correct |
27 |
Correct |
13 ms |
17804 KB |
Output is correct |
28 |
Correct |
13 ms |
17804 KB |
Output is correct |
29 |
Correct |
6 ms |
17804 KB |
Output is correct |
30 |
Correct |
16 ms |
17804 KB |
Output is correct |
31 |
Correct |
9 ms |
17804 KB |
Output is correct |
32 |
Correct |
9 ms |
17804 KB |
Output is correct |
33 |
Correct |
9 ms |
17804 KB |
Output is correct |
34 |
Correct |
13 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 |
16 ms |
17804 KB |
Output is correct |
39 |
Correct |
9 ms |
17804 KB |
Output is correct |
40 |
Correct |
13 ms |
17804 KB |
Output is correct |
41 |
Correct |
13 ms |
17804 KB |
Output is correct |
42 |
Correct |
6 ms |
17804 KB |
Output is correct |
43 |
Correct |
9 ms |
17804 KB |
Output is correct |
44 |
Correct |
13 ms |
17804 KB |
Output is correct |
45 |
Correct |
13 ms |
17804 KB |
Output is correct |
46 |
Correct |
16 ms |
17804 KB |
Output is correct |
47 |
Correct |
13 ms |
17804 KB |
Output is correct |
48 |
Correct |
13 ms |
17804 KB |
Output is correct |
49 |
Correct |
16 ms |
17804 KB |
Output is correct |
50 |
Correct |
13 ms |
17804 KB |
Output is correct |
51 |
Correct |
6 ms |
17804 KB |
Output is correct |
52 |
Correct |
16 ms |
17804 KB |
Output is correct |
53 |
Correct |
13 ms |
17804 KB |
Output is correct |
54 |
Correct |
16 ms |
17804 KB |
Output is correct |