#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif
#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
advance(it, -n);
return it;
}
template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
advance(it, n);
return it;
}
#endif
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;
const double EPS = 1e-9;
const double PI = 3.141592653589793238462;
template<typename T>
inline T sq(T a) { return a * a; }
//#ifdef LOCAL_MACHINE
//#endif
const int MAXN = 2e6 + 5;
const int BASE = 29;
const int MOD = 1e9 + 7;
inline int mul_mod(int a, int b) {
return a * 1LL * b % MOD;
}
inline void add_mod(int &a, int b) {
a += b;
if (a >= MOD) a -= MOD;
}
inline void sub_mod(int &a, int b) {
a -= b;
if (a < 0) a += MOD;
}
char str[MAXN];
int h[MAXN], bpow[MAXN];
int get_hash(int i, int j) {
if (i > j) return 0;
int ret = h[j];
sub_mod(ret, mul_mod(h[i - 1], bpow[j - i + 1]));
return ret;
}
int main() {
bpow[0] = 1;
for (int i = 1; i < MAXN; i++)
bpow[i] = mul_mod(bpow[i - 1], BASE);
//freopen("", "r", stdin);
//freopen("", "w", stdout);
int n;
scanf("%d", &n);
scanf("%s", str + 1);
if (!(n & 1)) {
puts("NOT POSSIBLE");
return 0;
}
for (int i = 1; i <= n; i++) {
h[i] = mul_mod(h[i - 1], BASE);
add_mod(h[i], str[i] - 'A' + 1);
}
set<int> sol;
int ans = -1, cnt = 0;
for (int i = 1; i <= n; i++) {
int left, right;
if (i <= (n / 2) + 1) {
left = get_hash(1, i - 1);
int len = (i - 1);
int rem = (n / 2) - len;
left = mul_mod(left, bpow[rem]);
add_mod(left, get_hash(i + 1, i + 1 + rem - 1));
assert(i + 1 + rem - 1 == n - (n / 2));
right = get_hash(n - (n / 2) + 1, n);
} else {
left = get_hash(1, n / 2);
int len = n - (i + 1) + 1;
int rem = (n / 2) - len;
right = get_hash((n / 2) + 1, (n / 2) + 1 + rem - 1);
right = mul_mod(right, bpow[len]);
add_mod(right, get_hash(i + 1, n));
}
if (left == right) {
sol.insert(left);
//cnt++;
ans = i;
//printf("I can replace char at pos %d\n", i);
}
}
cnt = (int)sol.size();
if (cnt > 1)
puts("NOT UNIQUE");
else if (cnt == 0)
puts("NOT POSSIBLE");
else {
for (int i = 1, c = 0; c < (n / 2); i++) {
if (ans == i) continue;
c++;
pc(str[i]);
}
pc('\n');
}
return 0;
}
Compilation message
friends.cpp: In function 'int main()':
friends.cpp:87:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
friends.cpp:88:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", str + 1);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
19600 KB |
Output is correct |
2 |
Correct |
16 ms |
19600 KB |
Output is correct |
3 |
Correct |
13 ms |
19600 KB |
Output is correct |
4 |
Correct |
13 ms |
19600 KB |
Output is correct |
5 |
Correct |
16 ms |
19600 KB |
Output is correct |
6 |
Correct |
16 ms |
19600 KB |
Output is correct |
7 |
Correct |
9 ms |
19600 KB |
Output is correct |
8 |
Correct |
13 ms |
19600 KB |
Output is correct |
9 |
Correct |
16 ms |
19600 KB |
Output is correct |
10 |
Correct |
9 ms |
19600 KB |
Output is correct |
11 |
Correct |
16 ms |
19600 KB |
Output is correct |
12 |
Correct |
16 ms |
19600 KB |
Output is correct |
13 |
Correct |
16 ms |
19600 KB |
Output is correct |
14 |
Correct |
13 ms |
19600 KB |
Output is correct |
15 |
Correct |
13 ms |
19600 KB |
Output is correct |
16 |
Correct |
13 ms |
19600 KB |
Output is correct |
17 |
Correct |
9 ms |
19600 KB |
Output is correct |
18 |
Correct |
13 ms |
19600 KB |
Output is correct |
19 |
Correct |
6 ms |
19600 KB |
Output is correct |
20 |
Correct |
16 ms |
19600 KB |
Output is correct |
21 |
Correct |
16 ms |
19600 KB |
Output is correct |
22 |
Correct |
16 ms |
19600 KB |
Output is correct |
23 |
Correct |
13 ms |
19600 KB |
Output is correct |
24 |
Correct |
13 ms |
19600 KB |
Output is correct |
25 |
Correct |
13 ms |
19600 KB |
Output is correct |
26 |
Correct |
16 ms |
19600 KB |
Output is correct |
27 |
Correct |
16 ms |
19600 KB |
Output is correct |
28 |
Correct |
13 ms |
19600 KB |
Output is correct |
29 |
Correct |
13 ms |
19600 KB |
Output is correct |
30 |
Correct |
19 ms |
19600 KB |
Output is correct |
31 |
Correct |
13 ms |
19600 KB |
Output is correct |
32 |
Correct |
13 ms |
19600 KB |
Output is correct |
33 |
Correct |
16 ms |
19600 KB |
Output is correct |
34 |
Correct |
16 ms |
19600 KB |
Output is correct |
35 |
Correct |
16 ms |
19600 KB |
Output is correct |
36 |
Correct |
13 ms |
19600 KB |
Output is correct |
37 |
Correct |
13 ms |
19600 KB |
Output is correct |
38 |
Correct |
16 ms |
19600 KB |
Output is correct |
39 |
Correct |
9 ms |
19600 KB |
Output is correct |
40 |
Correct |
6 ms |
19600 KB |
Output is correct |
41 |
Correct |
13 ms |
19600 KB |
Output is correct |
42 |
Correct |
13 ms |
19600 KB |
Output is correct |
43 |
Correct |
19 ms |
19600 KB |
Output is correct |
44 |
Correct |
19 ms |
19600 KB |
Output is correct |
45 |
Correct |
16 ms |
19600 KB |
Output is correct |
46 |
Correct |
9 ms |
19600 KB |
Output is correct |
47 |
Correct |
16 ms |
19600 KB |
Output is correct |
48 |
Correct |
9 ms |
19600 KB |
Output is correct |
49 |
Correct |
13 ms |
19600 KB |
Output is correct |
50 |
Correct |
16 ms |
19600 KB |
Output is correct |
51 |
Correct |
13 ms |
19600 KB |
Output is correct |
52 |
Correct |
19 ms |
19600 KB |
Output is correct |
53 |
Correct |
9 ms |
19600 KB |
Output is correct |
54 |
Correct |
9 ms |
19600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
96 ms |
19600 KB |
Output is correct |
2 |
Correct |
109 ms |
19600 KB |
Output is correct |
3 |
Correct |
116 ms |
19600 KB |
Output is correct |
4 |
Correct |
116 ms |
19600 KB |
Output is correct |
5 |
Correct |
103 ms |
19600 KB |
Output is correct |
6 |
Correct |
26 ms |
19600 KB |
Output is correct |
7 |
Correct |
106 ms |
19600 KB |
Output is correct |
8 |
Correct |
109 ms |
19600 KB |
Output is correct |
9 |
Correct |
99 ms |
19600 KB |
Output is correct |
10 |
Correct |
103 ms |
19600 KB |
Output is correct |
11 |
Correct |
83 ms |
19600 KB |
Output is correct |
12 |
Correct |
9 ms |
19600 KB |
Output is correct |
13 |
Correct |
13 ms |
19600 KB |
Output is correct |
14 |
Correct |
16 ms |
19600 KB |
Output is correct |
15 |
Correct |
13 ms |
19600 KB |
Output is correct |
16 |
Correct |
9 ms |
19600 KB |
Output is correct |
17 |
Correct |
16 ms |
19600 KB |
Output is correct |
18 |
Correct |
16 ms |
19600 KB |
Output is correct |
19 |
Correct |
9 ms |
19600 KB |
Output is correct |
20 |
Correct |
13 ms |
19600 KB |
Output is correct |
21 |
Correct |
16 ms |
19600 KB |
Output is correct |
22 |
Correct |
9 ms |
19600 KB |
Output is correct |
23 |
Correct |
16 ms |
19600 KB |
Output is correct |
24 |
Correct |
13 ms |
19600 KB |
Output is correct |
25 |
Correct |
9 ms |
19600 KB |
Output is correct |
26 |
Correct |
16 ms |
19600 KB |
Output is correct |
27 |
Correct |
13 ms |
19600 KB |
Output is correct |
28 |
Correct |
9 ms |
19600 KB |
Output is correct |
29 |
Correct |
16 ms |
19600 KB |
Output is correct |
30 |
Correct |
16 ms |
19600 KB |
Output is correct |
31 |
Correct |
13 ms |
19600 KB |
Output is correct |
32 |
Correct |
13 ms |
19600 KB |
Output is correct |
33 |
Correct |
16 ms |
19600 KB |
Output is correct |
34 |
Correct |
16 ms |
19600 KB |
Output is correct |
35 |
Correct |
6 ms |
19600 KB |
Output is correct |
36 |
Correct |
6 ms |
19600 KB |
Output is correct |
37 |
Correct |
9 ms |
19600 KB |
Output is correct |
38 |
Correct |
9 ms |
19600 KB |
Output is correct |
39 |
Correct |
16 ms |
19600 KB |
Output is correct |
40 |
Correct |
9 ms |
19600 KB |
Output is correct |
41 |
Correct |
16 ms |
19600 KB |
Output is correct |
42 |
Correct |
13 ms |
19600 KB |
Output is correct |
43 |
Correct |
16 ms |
19600 KB |
Output is correct |
44 |
Correct |
16 ms |
19600 KB |
Output is correct |
45 |
Correct |
16 ms |
19600 KB |
Output is correct |
46 |
Correct |
13 ms |
19600 KB |
Output is correct |
47 |
Correct |
16 ms |
19600 KB |
Output is correct |
48 |
Correct |
16 ms |
19600 KB |
Output is correct |
49 |
Correct |
16 ms |
19600 KB |
Output is correct |
50 |
Correct |
13 ms |
19600 KB |
Output is correct |
51 |
Correct |
16 ms |
19600 KB |
Output is correct |
52 |
Correct |
13 ms |
19600 KB |
Output is correct |
53 |
Correct |
13 ms |
19600 KB |
Output is correct |
54 |
Correct |
9 ms |
19600 KB |
Output is correct |