#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;
const int MAXN = 2001000;
ll ha[MAXN], pot[MAXN];
ll ha2[MAXN], pot2[MAXN];
const int BASE = 35537;
const int MOD = 1e9 + 7;
const int BASE2 = 57737;
const int MOD2 = 1e9 + 9;
ll val(int x, int y) {
if (y < x) return 0;
ll out = ha[y];
if (x) out = (((out - ha[x - 1] * pot[y - x + 1]) % MOD) + MOD) % MOD;
return out;
}
ll val2(int x, int y) {
if (y < x) return 0;
ll out = ha2[y];
if (x) out = (((out - ha2[x - 1] * pot2[y - x + 1]) % MOD2) + MOD2) % MOD2;
return out;
}
int main() {
ios_base::sync_with_stdio(false);
pot[0] = 1;
FOR(i, 1, MAXN) pot[i] = (pot[i - 1] * BASE) % MOD;
pot2[0] = 1;
FOR(i, 1, MAXN) pot2[i] = (pot2[i - 1] * BASE2) % MOD2;
int n;
cin >> n;
string s;
cin >> s;
if (n % 2 == 0) {
cout << "NOT POSSIBLE\n";
return 0;
}
ll curr = 0, curr2 = 0;
REP(i, n) {
curr = (curr * BASE + s[i]) % MOD;
ha[i] = curr;
curr2 = (curr2 * BASE2 + s[i]) % MOD2;
ha2[i] = curr2;
}
string out = "";
ll V = -1, V2 = -1;
REP(i, n) {
if (i <= n / 2) {
ll a = (val(0, i - 1) * pot[n / 2 - i] + val(i + 1, n / 2)) % MOD;
ll b = val(n / 2 + 1, n - 1);
ll a2 = (val2(0, i - 1) * pot2[n / 2 - i] + val2(i + 1, n / 2)) % MOD2;
ll b2 = val2(n / 2 + 1, n - 1);
if (a != b) continue;
if (a2 != b2) continue;
if (out != "" && (V != a || V2 != a2)) {
cout << "NOT UNIQUE\n";
return 0;
} else if (out == "") {
V = a;
V2 = a2;
out = s.substr(n / 2 + 1, n / 2);
}
} else {
ll a = val(0, n / 2 - 1);
ll b = (val(n / 2, i - 1) * pot[n - i - 1] + val(i + 1, n - 1)) % MOD;
ll a2 = val2(0, n / 2 - 1);
ll b2 = (val2(n / 2, i - 1) * pot2[n - i - 1] + val2(i + 1, n - 1)) % MOD2;
if (a != b) continue;
if (a2 != b2) continue;
if (out != "" && (V != a || V2 != a2)) {
cout << "NOT UNIQUE\n";
return 0;
} else if (out == "") {
V = a;
V2 = a2;
out = s.substr(0, n / 2);
}
}
}
if (out == "") cout << "NOT POSSIBLE\n";
else cout << out << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
31608 KB |
Output is correct |
2 |
Correct |
44 ms |
31608 KB |
Output is correct |
3 |
Correct |
46 ms |
31736 KB |
Output is correct |
4 |
Correct |
50 ms |
31628 KB |
Output is correct |
5 |
Correct |
48 ms |
31608 KB |
Output is correct |
6 |
Correct |
47 ms |
31608 KB |
Output is correct |
7 |
Correct |
49 ms |
31736 KB |
Output is correct |
8 |
Correct |
47 ms |
31736 KB |
Output is correct |
9 |
Correct |
44 ms |
31736 KB |
Output is correct |
10 |
Correct |
49 ms |
31608 KB |
Output is correct |
11 |
Correct |
45 ms |
31608 KB |
Output is correct |
12 |
Correct |
47 ms |
31608 KB |
Output is correct |
13 |
Correct |
48 ms |
31736 KB |
Output is correct |
14 |
Correct |
48 ms |
31608 KB |
Output is correct |
15 |
Correct |
48 ms |
31608 KB |
Output is correct |
16 |
Correct |
46 ms |
31736 KB |
Output is correct |
17 |
Correct |
62 ms |
31608 KB |
Output is correct |
18 |
Correct |
46 ms |
31640 KB |
Output is correct |
19 |
Correct |
49 ms |
31864 KB |
Output is correct |
20 |
Correct |
48 ms |
31736 KB |
Output is correct |
21 |
Correct |
47 ms |
31736 KB |
Output is correct |
22 |
Correct |
47 ms |
31736 KB |
Output is correct |
23 |
Correct |
47 ms |
31736 KB |
Output is correct |
24 |
Correct |
44 ms |
31608 KB |
Output is correct |
25 |
Correct |
51 ms |
31736 KB |
Output is correct |
26 |
Correct |
45 ms |
31608 KB |
Output is correct |
27 |
Correct |
49 ms |
31736 KB |
Output is correct |
28 |
Correct |
46 ms |
31608 KB |
Output is correct |
29 |
Correct |
46 ms |
31736 KB |
Output is correct |
30 |
Correct |
48 ms |
31736 KB |
Output is correct |
31 |
Correct |
46 ms |
31608 KB |
Output is correct |
32 |
Correct |
129 ms |
31608 KB |
Output is correct |
33 |
Correct |
50 ms |
31648 KB |
Output is correct |
34 |
Correct |
48 ms |
31708 KB |
Output is correct |
35 |
Correct |
57 ms |
31740 KB |
Output is correct |
36 |
Correct |
48 ms |
31636 KB |
Output is correct |
37 |
Correct |
46 ms |
31736 KB |
Output is correct |
38 |
Correct |
45 ms |
31744 KB |
Output is correct |
39 |
Correct |
45 ms |
31608 KB |
Output is correct |
40 |
Correct |
46 ms |
31708 KB |
Output is correct |
41 |
Correct |
71 ms |
31736 KB |
Output is correct |
42 |
Correct |
47 ms |
31736 KB |
Output is correct |
43 |
Correct |
50 ms |
31708 KB |
Output is correct |
44 |
Correct |
51 ms |
31736 KB |
Output is correct |
45 |
Correct |
48 ms |
31716 KB |
Output is correct |
46 |
Correct |
55 ms |
31864 KB |
Output is correct |
47 |
Correct |
50 ms |
31736 KB |
Output is correct |
48 |
Correct |
49 ms |
31736 KB |
Output is correct |
49 |
Correct |
47 ms |
31608 KB |
Output is correct |
50 |
Correct |
47 ms |
31736 KB |
Output is correct |
51 |
Correct |
51 ms |
31736 KB |
Output is correct |
52 |
Correct |
48 ms |
31736 KB |
Output is correct |
53 |
Correct |
46 ms |
31736 KB |
Output is correct |
54 |
Correct |
46 ms |
31736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
147 ms |
66968 KB |
Output is correct |
2 |
Correct |
170 ms |
66936 KB |
Output is correct |
3 |
Correct |
139 ms |
66884 KB |
Output is correct |
4 |
Correct |
153 ms |
66844 KB |
Output is correct |
5 |
Correct |
150 ms |
66920 KB |
Output is correct |
6 |
Correct |
51 ms |
33820 KB |
Output is correct |
7 |
Correct |
191 ms |
66980 KB |
Output is correct |
8 |
Correct |
137 ms |
62488 KB |
Output is correct |
9 |
Correct |
137 ms |
63344 KB |
Output is correct |
10 |
Correct |
137 ms |
63484 KB |
Output is correct |
11 |
Correct |
127 ms |
59640 KB |
Output is correct |
12 |
Correct |
46 ms |
31708 KB |
Output is correct |
13 |
Correct |
56 ms |
31608 KB |
Output is correct |
14 |
Correct |
47 ms |
31736 KB |
Output is correct |
15 |
Correct |
46 ms |
31608 KB |
Output is correct |
16 |
Correct |
47 ms |
31608 KB |
Output is correct |
17 |
Correct |
47 ms |
31688 KB |
Output is correct |
18 |
Correct |
45 ms |
31736 KB |
Output is correct |
19 |
Correct |
46 ms |
31736 KB |
Output is correct |
20 |
Correct |
49 ms |
31736 KB |
Output is correct |
21 |
Correct |
47 ms |
31608 KB |
Output is correct |
22 |
Correct |
47 ms |
31608 KB |
Output is correct |
23 |
Correct |
54 ms |
31608 KB |
Output is correct |
24 |
Correct |
47 ms |
31864 KB |
Output is correct |
25 |
Correct |
48 ms |
31608 KB |
Output is correct |
26 |
Correct |
45 ms |
31736 KB |
Output is correct |
27 |
Correct |
48 ms |
31736 KB |
Output is correct |
28 |
Correct |
45 ms |
31608 KB |
Output is correct |
29 |
Correct |
46 ms |
31736 KB |
Output is correct |
30 |
Correct |
46 ms |
31608 KB |
Output is correct |
31 |
Correct |
47 ms |
31628 KB |
Output is correct |
32 |
Correct |
50 ms |
31736 KB |
Output is correct |
33 |
Correct |
46 ms |
31608 KB |
Output is correct |
34 |
Correct |
47 ms |
31736 KB |
Output is correct |
35 |
Correct |
47 ms |
31636 KB |
Output is correct |
36 |
Correct |
50 ms |
31736 KB |
Output is correct |
37 |
Correct |
46 ms |
31608 KB |
Output is correct |
38 |
Correct |
45 ms |
31736 KB |
Output is correct |
39 |
Correct |
45 ms |
31608 KB |
Output is correct |
40 |
Correct |
45 ms |
31736 KB |
Output is correct |
41 |
Correct |
45 ms |
31736 KB |
Output is correct |
42 |
Correct |
51 ms |
31740 KB |
Output is correct |
43 |
Correct |
47 ms |
31736 KB |
Output is correct |
44 |
Correct |
48 ms |
31724 KB |
Output is correct |
45 |
Correct |
46 ms |
31692 KB |
Output is correct |
46 |
Correct |
50 ms |
31608 KB |
Output is correct |
47 |
Correct |
45 ms |
31656 KB |
Output is correct |
48 |
Correct |
47 ms |
31736 KB |
Output is correct |
49 |
Correct |
46 ms |
31608 KB |
Output is correct |
50 |
Correct |
45 ms |
31636 KB |
Output is correct |
51 |
Correct |
50 ms |
31608 KB |
Output is correct |
52 |
Correct |
45 ms |
31608 KB |
Output is correct |
53 |
Correct |
49 ms |
31736 KB |
Output is correct |
54 |
Correct |
46 ms |
31736 KB |
Output is correct |