#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define int long long // LEMBRAR DE TROCAR CASO PROBLEMA DE MEMORIA
#define pii pair<int,int>
#define eps (int) 1e9
#define mp make_pair
#define pb push_back
int base = 57 , mod = 1000000007 , ivi = 58394161;
int hs[3000000], pot[3000000] , inv[3000000];
int gethash(int l , int r){
if(l > r) return 0;
int hashlow = hs[r];
if(l) hashlow -= hs[l-1];
hashlow += mod*mod;
hashlow %= mod;
hashlow *= inv[l];
hashlow %= mod;
return hashlow;
}
int binaryexpo(int x , int y){
if(x == 0) return 0;
if(y==0)return 1;
if(y == 1) return x;
int pp = binaryexpo(x , y/2);
pp *= pp;
pp %= mod;
if(y %2) pp*=x;
pp%= mod;
return pp;
}
int32_t main(){
/*ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
*/
int n;
scanf("%lld" , &n);
string s;
s.resize(n);
scanf("%s" , &s[0]);
if(n%2 == 0 || n == 1){
printf("NOT POSSIBLE\n");
return 0;
}
ivi = binaryexpo(base , mod - 2);
pot[0] = 1 , pot[1] = base, inv[0] = 1 , inv[1] = ivi;
for(int i = 2 ; i < 3000000; i ++){
pot[i] = pot[i-1] * base;
inv[i] = inv[i-1] * ivi;
inv[i] %= mod;
pot[i] %= mod;
}
hs[0] = (s[0] - 'A' + 1);
for(int i = 1 ; i < n; i ++){
hs[i] = (s[i] - 'A' + 1)*pot[i];
hs[i] += hs[i-1];
hs[i] += mod*mod;
hs[i] %= mod;
}
vector<int> can_r;
set<int> hashz;
for(int i = 0 ; i < n; i ++){
if(n/2 == i){
if(gethash(0 , i-1) == gethash(i + 1 , n-1)) can_r.pb(i), hashz.insert(gethash(0 , i-1));
}
if(i < n/2){
if((gethash(n/2 + 1 , n-1)%mod) == ((gethash(0 , i -1) + gethash(i + 1 , n/2)*pot[i])%mod)) can_r.pb(i) , hashz.insert(gethash(n/2 + 1 , n - 1)%mod);
}
if(i > n/2){
if((gethash(0 , n/2 - 1)%mod) == ( (gethash(n/2 , i-1) + gethash(i + 1 , n -1)*pot[i - n/2]))) can_r.pb(i) , hashz.insert(gethash(0 , n/2 - 1)%mod) ;
}
}
if(hashz.size() == 0) printf("NOT POSSIBLE\n");
if(hashz.size() > 1) printf("NOT UNIQUE\n");
if(hashz.size() == 1){
int conta = n - 1;
conta /= 2;
int tt = 0;
while(conta){
if(tt++ == can_r[0]) continue;
printf("%c" , s[tt-1]);
conta--;
}
}
}
Compilation message
friends.cpp: In function 'int32_t main()':
friends.cpp:41:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld" , &n);
^
friends.cpp:44:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s" , &s[0]);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
89 ms |
72332 KB |
Output is correct |
2 |
Correct |
83 ms |
72332 KB |
Output is correct |
3 |
Correct |
86 ms |
72332 KB |
Output is correct |
4 |
Correct |
86 ms |
72332 KB |
Output is correct |
5 |
Correct |
83 ms |
72332 KB |
Output is correct |
6 |
Correct |
83 ms |
72332 KB |
Output is correct |
7 |
Correct |
86 ms |
72332 KB |
Output is correct |
8 |
Correct |
83 ms |
72332 KB |
Output is correct |
9 |
Correct |
99 ms |
72332 KB |
Output is correct |
10 |
Correct |
89 ms |
72332 KB |
Output is correct |
11 |
Correct |
83 ms |
72332 KB |
Output is correct |
12 |
Correct |
89 ms |
72332 KB |
Output is correct |
13 |
Correct |
83 ms |
72332 KB |
Output is correct |
14 |
Correct |
103 ms |
72332 KB |
Output is correct |
15 |
Correct |
83 ms |
72332 KB |
Output is correct |
16 |
Correct |
69 ms |
72332 KB |
Output is correct |
17 |
Correct |
86 ms |
72332 KB |
Output is correct |
18 |
Correct |
79 ms |
72332 KB |
Output is correct |
19 |
Correct |
99 ms |
72332 KB |
Output is correct |
20 |
Correct |
93 ms |
72332 KB |
Output is correct |
21 |
Correct |
79 ms |
72332 KB |
Output is correct |
22 |
Correct |
86 ms |
72332 KB |
Output is correct |
23 |
Correct |
63 ms |
72332 KB |
Output is correct |
24 |
Correct |
0 ms |
72332 KB |
Output is correct |
25 |
Correct |
0 ms |
72332 KB |
Output is correct |
26 |
Correct |
0 ms |
72332 KB |
Output is correct |
27 |
Correct |
76 ms |
72332 KB |
Output is correct |
28 |
Correct |
86 ms |
72332 KB |
Output is correct |
29 |
Correct |
96 ms |
72332 KB |
Output is correct |
30 |
Correct |
86 ms |
72332 KB |
Output is correct |
31 |
Correct |
93 ms |
72332 KB |
Output is correct |
32 |
Correct |
76 ms |
72332 KB |
Output is correct |
33 |
Correct |
83 ms |
72332 KB |
Output is correct |
34 |
Correct |
86 ms |
72332 KB |
Output is correct |
35 |
Correct |
86 ms |
72332 KB |
Output is correct |
36 |
Correct |
76 ms |
72332 KB |
Output is correct |
37 |
Correct |
76 ms |
72332 KB |
Output is correct |
38 |
Correct |
86 ms |
72332 KB |
Output is correct |
39 |
Correct |
79 ms |
72332 KB |
Output is correct |
40 |
Correct |
86 ms |
72332 KB |
Output is correct |
41 |
Correct |
56 ms |
72332 KB |
Output is correct |
42 |
Correct |
93 ms |
72332 KB |
Output is correct |
43 |
Correct |
93 ms |
72332 KB |
Output is correct |
44 |
Correct |
79 ms |
72332 KB |
Output is correct |
45 |
Correct |
93 ms |
72332 KB |
Output is correct |
46 |
Correct |
89 ms |
72332 KB |
Output is correct |
47 |
Correct |
76 ms |
72332 KB |
Output is correct |
48 |
Correct |
93 ms |
72332 KB |
Output is correct |
49 |
Correct |
0 ms |
72332 KB |
Output is correct |
50 |
Correct |
96 ms |
72332 KB |
Output is correct |
51 |
Correct |
79 ms |
72332 KB |
Output is correct |
52 |
Correct |
93 ms |
72332 KB |
Output is correct |
53 |
Correct |
86 ms |
72332 KB |
Output is correct |
54 |
Correct |
66 ms |
72332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
463 ms |
74288 KB |
Output is correct |
2 |
Correct |
419 ms |
74288 KB |
Output is correct |
3 |
Correct |
439 ms |
74288 KB |
Output is correct |
4 |
Correct |
466 ms |
74288 KB |
Output is correct |
5 |
Correct |
419 ms |
74288 KB |
Output is correct |
6 |
Correct |
3 ms |
74288 KB |
Output is correct |
7 |
Correct |
499 ms |
86660 KB |
Output is correct |
8 |
Correct |
359 ms |
74092 KB |
Output is correct |
9 |
Correct |
426 ms |
74092 KB |
Output is correct |
10 |
Correct |
376 ms |
74092 KB |
Output is correct |
11 |
Correct |
369 ms |
73960 KB |
Output is correct |
12 |
Correct |
123 ms |
72332 KB |
Output is correct |
13 |
Correct |
86 ms |
72332 KB |
Output is correct |
14 |
Correct |
93 ms |
72332 KB |
Output is correct |
15 |
Correct |
83 ms |
72332 KB |
Output is correct |
16 |
Correct |
73 ms |
72332 KB |
Output is correct |
17 |
Correct |
86 ms |
72332 KB |
Output is correct |
18 |
Correct |
69 ms |
72332 KB |
Output is correct |
19 |
Correct |
103 ms |
72332 KB |
Output is correct |
20 |
Correct |
76 ms |
72332 KB |
Output is correct |
21 |
Correct |
73 ms |
72332 KB |
Output is correct |
22 |
Correct |
93 ms |
72332 KB |
Output is correct |
23 |
Correct |
83 ms |
72332 KB |
Output is correct |
24 |
Correct |
83 ms |
72332 KB |
Output is correct |
25 |
Correct |
73 ms |
72332 KB |
Output is correct |
26 |
Correct |
73 ms |
72332 KB |
Output is correct |
27 |
Correct |
79 ms |
72332 KB |
Output is correct |
28 |
Correct |
76 ms |
72332 KB |
Output is correct |
29 |
Correct |
86 ms |
72332 KB |
Output is correct |
30 |
Correct |
83 ms |
72332 KB |
Output is correct |
31 |
Correct |
79 ms |
72332 KB |
Output is correct |
32 |
Correct |
83 ms |
72332 KB |
Output is correct |
33 |
Correct |
93 ms |
72332 KB |
Output is correct |
34 |
Correct |
69 ms |
72332 KB |
Output is correct |
35 |
Correct |
0 ms |
72332 KB |
Output is correct |
36 |
Correct |
0 ms |
72332 KB |
Output is correct |
37 |
Correct |
0 ms |
72332 KB |
Output is correct |
38 |
Correct |
76 ms |
72332 KB |
Output is correct |
39 |
Correct |
83 ms |
72332 KB |
Output is correct |
40 |
Correct |
79 ms |
72332 KB |
Output is correct |
41 |
Correct |
83 ms |
72332 KB |
Output is correct |
42 |
Correct |
73 ms |
72332 KB |
Output is correct |
43 |
Correct |
79 ms |
72332 KB |
Output is correct |
44 |
Correct |
93 ms |
72332 KB |
Output is correct |
45 |
Correct |
83 ms |
72332 KB |
Output is correct |
46 |
Correct |
79 ms |
72332 KB |
Output is correct |
47 |
Correct |
86 ms |
72332 KB |
Output is correct |
48 |
Correct |
99 ms |
72332 KB |
Output is correct |
49 |
Correct |
83 ms |
72332 KB |
Output is correct |
50 |
Correct |
86 ms |
72332 KB |
Output is correct |
51 |
Correct |
73 ms |
72332 KB |
Output is correct |
52 |
Correct |
83 ms |
72332 KB |
Output is correct |
53 |
Correct |
86 ms |
72332 KB |
Output is correct |
54 |
Correct |
83 ms |
72332 KB |
Output is correct |