#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1<<21;
const unsigned long long B1 = 139, B2 = 137, MOD = (1e9) + 696969;
struct rolling_hash {
unsigned long long h1,h2;
void initialize() {
h1=0;
h2=0;
}
void append(char a) {
h1*=B1;h1+=a-'A'+1;h1%=MOD;
h2*=B2;h2+=a-'A'+1;h2%=MOD;
}
bool operator ==(const rolling_hash &a) const {
return h1==a.h1 && h2==a.h2;
}
bool operator <(const rolling_hash &a) const {
return ((h1==a.h1) ? h2<a.h2 : h1<a.h2);
}
};
int tests,current_case;
int n;
unsigned long long pw1[N],pw2[N];
rolling_hash ph[N];
int ans[N],sz;
rolling_hash h1,h2;
char a[N];
rolling_hash h;
int cnt;
set < rolling_hash > s;
void message(int current_case) {
//cerr<<"Case "<<current_case<<" solved!"<<endl;
fprintf(stderr, "Case %d solved!\n", current_case);
}
rolling_hash merge_hashes(rolling_hash a, rolling_hash b, int length) {
a.h1*=pw1[length];
a.h1+=b.h1;
a.h1%=MOD;
a.h2*=pw2[length];
a.h2+=b.h2;
a.h2%=MOD;
return a;
}
rolling_hash get_hash(int l, int r) {
rolling_hash hl=ph[l-1],hr=ph[r];
hl.h1*=pw1[r-l+1];
hl.h1%=MOD;
hl.h2*=pw2[r-l+1];
hl.h2%=MOD;
hr.h1-=hl.h1;
hr.h1+=MOD;
hr.h1%=MOD;
hr.h2-=hl.h2;
hr.h2+=MOD;
hr.h2%=MOD;
return hr;
}
int main() {
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
int i;
pw1[0]=1;
pw2[0]=1;
for(i=1;i<N;i++) pw1[i]=pw1[i-1]*B1%MOD,pw2[i]=pw2[i-1]*B2%MOD;
tests=1;
//scanf("%d", &tests);
//cin>>tests;
for(current_case=1;current_case<=tests;current_case++) {
s.clear();
scanf("%d", &n);
scanf("%s", a+1);
h.initialize();
ph[0]=h;
for(i=1;i<=n;i++) h.append(a[i]),ph[i]=h;
if(!(n&1)){
printf("NOT POSSIBLE\n");
goto MESSAGE;
}
sz=0;
for(i=1;i<=n;i++) {
if(i>n/2) h1=get_hash(1,n/2);
else h1=merge_hashes(get_hash(1,i-1),get_hash(i+1,n/2+1),n/2+1-(i+1)+1);
if(i<n-n/2+1) h2=get_hash(n-n/2+1,n);
else h2=merge_hashes(get_hash(n-n/2,i-1),get_hash(i+1,n),n-i);
if(h1==h2) ans[++sz]=i,s.insert(h1);
}
sz=(int)(s.size());
if(sz==0) {
printf("NOT POSSIBLE\n");
goto MESSAGE;
}
else if(sz>1) {
printf("NOT UNIQUE\n");
goto MESSAGE;
}
cnt=0;
for(i=1;cnt<n/2;i++) {
if(i==ans[1]) continue;
++cnt;
printf("%c", a[i]);
}
printf("\n");
MESSAGE:
message(current_case);
}
return 0;
}
Compilation message
friends.cpp: In function 'int main()':
friends.cpp:82:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
^
friends.cpp:83:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", a+1);
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
77800 KB |
Output is correct |
2 |
Correct |
16 ms |
77800 KB |
Output is correct |
3 |
Correct |
13 ms |
77800 KB |
Output is correct |
4 |
Correct |
13 ms |
77800 KB |
Output is correct |
5 |
Correct |
13 ms |
77800 KB |
Output is correct |
6 |
Correct |
9 ms |
77800 KB |
Output is correct |
7 |
Correct |
23 ms |
77800 KB |
Output is correct |
8 |
Correct |
19 ms |
77800 KB |
Output is correct |
9 |
Correct |
23 ms |
77800 KB |
Output is correct |
10 |
Correct |
19 ms |
77800 KB |
Output is correct |
11 |
Correct |
13 ms |
77800 KB |
Output is correct |
12 |
Correct |
9 ms |
77800 KB |
Output is correct |
13 |
Correct |
13 ms |
77800 KB |
Output is correct |
14 |
Correct |
6 ms |
77800 KB |
Output is correct |
15 |
Correct |
13 ms |
77800 KB |
Output is correct |
16 |
Correct |
13 ms |
77800 KB |
Output is correct |
17 |
Correct |
16 ms |
77800 KB |
Output is correct |
18 |
Correct |
13 ms |
77800 KB |
Output is correct |
19 |
Correct |
13 ms |
77800 KB |
Output is correct |
20 |
Correct |
13 ms |
77800 KB |
Output is correct |
21 |
Correct |
13 ms |
77800 KB |
Output is correct |
22 |
Correct |
6 ms |
77800 KB |
Output is correct |
23 |
Correct |
13 ms |
77800 KB |
Output is correct |
24 |
Correct |
19 ms |
77800 KB |
Output is correct |
25 |
Correct |
13 ms |
77800 KB |
Output is correct |
26 |
Correct |
16 ms |
77800 KB |
Output is correct |
27 |
Correct |
9 ms |
77800 KB |
Output is correct |
28 |
Correct |
9 ms |
77800 KB |
Output is correct |
29 |
Correct |
6 ms |
77800 KB |
Output is correct |
30 |
Correct |
16 ms |
77800 KB |
Output is correct |
31 |
Correct |
9 ms |
77800 KB |
Output is correct |
32 |
Correct |
16 ms |
77800 KB |
Output is correct |
33 |
Correct |
13 ms |
77800 KB |
Output is correct |
34 |
Correct |
6 ms |
77800 KB |
Output is correct |
35 |
Correct |
9 ms |
77800 KB |
Output is correct |
36 |
Correct |
13 ms |
77800 KB |
Output is correct |
37 |
Correct |
16 ms |
77800 KB |
Output is correct |
38 |
Correct |
6 ms |
77800 KB |
Output is correct |
39 |
Correct |
9 ms |
77800 KB |
Output is correct |
40 |
Correct |
13 ms |
77800 KB |
Output is correct |
41 |
Correct |
16 ms |
77800 KB |
Output is correct |
42 |
Correct |
19 ms |
77800 KB |
Output is correct |
43 |
Correct |
13 ms |
77800 KB |
Output is correct |
44 |
Correct |
6 ms |
77800 KB |
Output is correct |
45 |
Correct |
9 ms |
77800 KB |
Output is correct |
46 |
Correct |
16 ms |
77800 KB |
Output is correct |
47 |
Correct |
16 ms |
77800 KB |
Output is correct |
48 |
Correct |
6 ms |
77800 KB |
Output is correct |
49 |
Correct |
9 ms |
77800 KB |
Output is correct |
50 |
Correct |
9 ms |
77800 KB |
Output is correct |
51 |
Correct |
13 ms |
77800 KB |
Output is correct |
52 |
Correct |
9 ms |
77800 KB |
Output is correct |
53 |
Correct |
13 ms |
77800 KB |
Output is correct |
54 |
Correct |
19 ms |
77800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
77800 KB |
Output is correct |
2 |
Correct |
149 ms |
77800 KB |
Output is correct |
3 |
Correct |
163 ms |
77800 KB |
Output is correct |
4 |
Correct |
136 ms |
77800 KB |
Output is correct |
5 |
Correct |
196 ms |
77800 KB |
Output is correct |
6 |
Correct |
26 ms |
77800 KB |
Output is correct |
7 |
Correct |
186 ms |
77800 KB |
Output is correct |
8 |
Correct |
103 ms |
77800 KB |
Output is correct |
9 |
Correct |
149 ms |
77800 KB |
Output is correct |
10 |
Correct |
146 ms |
77800 KB |
Output is correct |
11 |
Correct |
73 ms |
77800 KB |
Output is correct |
12 |
Correct |
13 ms |
77800 KB |
Output is correct |
13 |
Correct |
13 ms |
77800 KB |
Output is correct |
14 |
Correct |
9 ms |
77800 KB |
Output is correct |
15 |
Correct |
9 ms |
77800 KB |
Output is correct |
16 |
Correct |
13 ms |
77800 KB |
Output is correct |
17 |
Correct |
16 ms |
77800 KB |
Output is correct |
18 |
Correct |
19 ms |
77800 KB |
Output is correct |
19 |
Correct |
16 ms |
77800 KB |
Output is correct |
20 |
Correct |
9 ms |
77800 KB |
Output is correct |
21 |
Correct |
9 ms |
77800 KB |
Output is correct |
22 |
Correct |
6 ms |
77800 KB |
Output is correct |
23 |
Correct |
3 ms |
77800 KB |
Output is correct |
24 |
Correct |
9 ms |
77800 KB |
Output is correct |
25 |
Correct |
19 ms |
77800 KB |
Output is correct |
26 |
Correct |
23 ms |
77800 KB |
Output is correct |
27 |
Correct |
9 ms |
77800 KB |
Output is correct |
28 |
Correct |
13 ms |
77800 KB |
Output is correct |
29 |
Correct |
13 ms |
77800 KB |
Output is correct |
30 |
Correct |
6 ms |
77800 KB |
Output is correct |
31 |
Correct |
6 ms |
77800 KB |
Output is correct |
32 |
Correct |
23 ms |
77800 KB |
Output is correct |
33 |
Correct |
9 ms |
77800 KB |
Output is correct |
34 |
Correct |
9 ms |
77800 KB |
Output is correct |
35 |
Correct |
16 ms |
77800 KB |
Output is correct |
36 |
Correct |
9 ms |
77800 KB |
Output is correct |
37 |
Correct |
13 ms |
77800 KB |
Output is correct |
38 |
Correct |
13 ms |
77800 KB |
Output is correct |
39 |
Correct |
6 ms |
77800 KB |
Output is correct |
40 |
Correct |
9 ms |
77800 KB |
Output is correct |
41 |
Correct |
19 ms |
77800 KB |
Output is correct |
42 |
Correct |
13 ms |
77800 KB |
Output is correct |
43 |
Correct |
9 ms |
77800 KB |
Output is correct |
44 |
Correct |
9 ms |
77800 KB |
Output is correct |
45 |
Correct |
23 ms |
77800 KB |
Output is correct |
46 |
Correct |
16 ms |
77800 KB |
Output is correct |
47 |
Correct |
19 ms |
77800 KB |
Output is correct |
48 |
Correct |
16 ms |
77800 KB |
Output is correct |
49 |
Correct |
19 ms |
77800 KB |
Output is correct |
50 |
Correct |
16 ms |
77800 KB |
Output is correct |
51 |
Correct |
16 ms |
77800 KB |
Output is correct |
52 |
Correct |
16 ms |
77800 KB |
Output is correct |
53 |
Correct |
3 ms |
77800 KB |
Output is correct |
54 |
Correct |
16 ms |
77800 KB |
Output is correct |