#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long mod = 2147483647;
int N; string S;
long long power[1 << 21];
long long hush[1 << 21];
void init() {
power[0] = 1;
for (int i = 1; i <= 2010000; i++) power[i] = 217LL * power[i - 1] % mod;
for (int i = 1; i <= S.size(); i++) hush[i] = (217LL * hush[i - 1] + (long long)(S[i - 1] - 'A' + 1)) % mod;
}
long long getval(int l, int r) {
return (hush[r] - (hush[l] * power[r - l]) + mod * mod) % mod;
}
int main() {
cin >> N >> S; init();
if (N % 2 == 0) {
cout << "NOT POSSIBLE" << endl;
return 0;
}
vector<long long> val; int turn = 0;
for (int i = 0; i < N; i++) {
long long s1, s2;
if (i < N / 2) {
s1 = getval(0, i) * power[(N / 2) - i] + getval(i + 1, (N / 2) + 1); s1 %= mod;
s2 = getval((N / 2) + 1, N);
}
else if (i == N / 2) {
s1 = getval(0, i);
s2 = getval(i + 1, N);
}
else {
s1 = getval(0, N / 2);
s2 = getval(N / 2, i) * power[N - i - 1] + getval(i + 1, N); s2 %= mod;
}
if (s1 == s2) { val.push_back(s1); turn = i; }
}
sort(val.begin(), val.end());
val.erase(unique(val.begin(), val.end()), val.end());
if (val.size() == 0) cout << "NOT POSSIBLE" << endl;
if (val.size() >= 2) cout << "NOT UNIQUE" << endl;
if (val.size() == 1) {
if (turn <= N / 2) cout << S.substr((N / 2) + 1, N - ((N / 2) + 1)) << endl;
else cout << S.substr(0, N / 2) << endl;
}
return 0;
}
Compilation message
friends.cpp: In function 'void init()':
friends.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i <= S.size(); i++) hush[i] = (217LL * hush[i - 1] + (long long)(S[i - 1] - 'A' + 1)) % mod;
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 2 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 3 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 4 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 5 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 6 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 7 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 8 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 9 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 10 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 11 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 12 |
Correct |
29 ms |
16120 KB |
Output is correct |
| 13 |
Correct |
28 ms |
16096 KB |
Output is correct |
| 14 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 15 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 16 |
Correct |
27 ms |
16120 KB |
Output is correct |
| 17 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 18 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 19 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 20 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 21 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 22 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 23 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 24 |
Correct |
27 ms |
16012 KB |
Output is correct |
| 25 |
Correct |
27 ms |
15996 KB |
Output is correct |
| 26 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 27 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 28 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 29 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 30 |
Correct |
28 ms |
16172 KB |
Output is correct |
| 31 |
Correct |
28 ms |
16096 KB |
Output is correct |
| 32 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 33 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 34 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 35 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 36 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 37 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 38 |
Correct |
27 ms |
16120 KB |
Output is correct |
| 39 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 40 |
Correct |
27 ms |
15996 KB |
Output is correct |
| 41 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 42 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 43 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 44 |
Correct |
27 ms |
16120 KB |
Output is correct |
| 45 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 46 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 47 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 48 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 49 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 50 |
Correct |
27 ms |
16120 KB |
Output is correct |
| 51 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 52 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 53 |
Correct |
29 ms |
16120 KB |
Output is correct |
| 54 |
Correct |
27 ms |
16120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
242 ms |
35680 KB |
Output is correct |
| 2 |
Correct |
244 ms |
35680 KB |
Output is correct |
| 3 |
Correct |
241 ms |
35680 KB |
Output is correct |
| 4 |
Correct |
245 ms |
35680 KB |
Output is correct |
| 5 |
Correct |
243 ms |
35808 KB |
Output is correct |
| 6 |
Correct |
154 ms |
33760 KB |
Output is correct |
| 7 |
Correct |
295 ms |
52440 KB |
Output is correct |
| 8 |
Correct |
221 ms |
32224 KB |
Output is correct |
| 9 |
Correct |
218 ms |
33768 KB |
Output is correct |
| 10 |
Correct |
222 ms |
33768 KB |
Output is correct |
| 11 |
Correct |
215 ms |
30824 KB |
Output is correct |
| 12 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 13 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 14 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 15 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 16 |
Correct |
28 ms |
16104 KB |
Output is correct |
| 17 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 18 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 19 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 20 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 21 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 22 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 23 |
Correct |
29 ms |
16248 KB |
Output is correct |
| 24 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 25 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 26 |
Correct |
29 ms |
16120 KB |
Output is correct |
| 27 |
Correct |
27 ms |
16120 KB |
Output is correct |
| 28 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 29 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 30 |
Correct |
29 ms |
15992 KB |
Output is correct |
| 31 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 32 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 33 |
Correct |
29 ms |
15992 KB |
Output is correct |
| 34 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 35 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 36 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 37 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 38 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 39 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 40 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 41 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 42 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 43 |
Correct |
30 ms |
15992 KB |
Output is correct |
| 44 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 45 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 46 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 47 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 48 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 49 |
Correct |
27 ms |
15992 KB |
Output is correct |
| 50 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 51 |
Correct |
28 ms |
16120 KB |
Output is correct |
| 52 |
Correct |
27 ms |
16120 KB |
Output is correct |
| 53 |
Correct |
28 ms |
15992 KB |
Output is correct |
| 54 |
Correct |
28 ms |
15996 KB |
Output is correct |
