#include <bits/stdc++.h>
using namespace std;
#define int long long
int const N=3e6+5;
int const mod=1e9+9;
int const base=727;
int Hash[N];
int pw[N];
int n;
string s;
void pre(){
pw[0]=1;
for(int i=1;i<N;i++)
pw[i]=(pw[i-1]*base)%mod;
}
void make_Hash(){
for(int i=1;i<=n;i++)
Hash[i]=(((Hash[i-1]*base)%mod)+s[i-1])%mod;
}
int compute_Hash(int l,int r){
return ((Hash[r] - ((Hash[l]*pw[r-l])%mod) )+mod)%mod;
}
int org_Hash1(int e){
if(e>n/2)
return Hash[n/2];
int h=(Hash[e-1]*pw[((n/2)+1)-e])%mod;
h+=compute_Hash(e,(n/2)+1);
h%=mod;
return h;
}
int org_Hash2(int e){
if(e<=(n/2)+1)
return compute_Hash((n/2)+1,n);
int h=(compute_Hash((n/2),e-1)*pw[n-e])%mod;
h+=compute_Hash(e,n);
h%=mod;
return h;
}
string make_str(int p){
string st="";
int sz=0;
int i=0;
while(i<=n && sz<(n/2)){
i++;
if(i==p)
continue;
st+=s[i-1];
sz++;
}
return st;
}
signed main()
{
cin>>n;
cin>>s;
if(n%2==0){
cout<<"NOT POSSIBLE\n";
return 0;
}
bool b=0;
for(int i=1;i<n;i++)
if(s[i]!=s[i-1])
b=1;
pre();
make_Hash();
int rem=0;
int cnt=0;
for(int i=1;i<=n;i++){
if(org_Hash1(i)==org_Hash2(i)){
rem=i;
cnt++;
}
}
if(cnt==0)
cout<<"NOT POSSIBLE"<<endl;
else if(cnt>1 && b)
cout<<"NOT UNIQUE"<<endl;
else
cout<<make_str(rem)<<endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
25176 KB |
Output is correct |
2 |
Correct |
16 ms |
25180 KB |
Output is correct |
3 |
Correct |
18 ms |
25180 KB |
Output is correct |
4 |
Correct |
18 ms |
25180 KB |
Output is correct |
5 |
Correct |
16 ms |
25176 KB |
Output is correct |
6 |
Correct |
18 ms |
25180 KB |
Output is correct |
7 |
Correct |
16 ms |
25180 KB |
Output is correct |
8 |
Correct |
16 ms |
25196 KB |
Output is correct |
9 |
Correct |
16 ms |
25204 KB |
Output is correct |
10 |
Correct |
16 ms |
25200 KB |
Output is correct |
11 |
Correct |
17 ms |
25180 KB |
Output is correct |
12 |
Correct |
16 ms |
25180 KB |
Output is correct |
13 |
Correct |
16 ms |
25176 KB |
Output is correct |
14 |
Correct |
17 ms |
25216 KB |
Output is correct |
15 |
Correct |
16 ms |
25180 KB |
Output is correct |
16 |
Correct |
16 ms |
25200 KB |
Output is correct |
17 |
Correct |
16 ms |
25180 KB |
Output is correct |
18 |
Correct |
16 ms |
25180 KB |
Output is correct |
19 |
Correct |
17 ms |
25180 KB |
Output is correct |
20 |
Correct |
16 ms |
25176 KB |
Output is correct |
21 |
Correct |
16 ms |
25176 KB |
Output is correct |
22 |
Correct |
16 ms |
25180 KB |
Output is correct |
23 |
Correct |
16 ms |
25176 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
17 ms |
25180 KB |
Output is correct |
28 |
Correct |
16 ms |
25180 KB |
Output is correct |
29 |
Correct |
16 ms |
25180 KB |
Output is correct |
30 |
Correct |
16 ms |
25180 KB |
Output is correct |
31 |
Correct |
17 ms |
25376 KB |
Output is correct |
32 |
Correct |
16 ms |
25180 KB |
Output is correct |
33 |
Correct |
16 ms |
25216 KB |
Output is correct |
34 |
Correct |
16 ms |
25180 KB |
Output is correct |
35 |
Correct |
16 ms |
25180 KB |
Output is correct |
36 |
Correct |
16 ms |
25180 KB |
Output is correct |
37 |
Correct |
16 ms |
25180 KB |
Output is correct |
38 |
Correct |
16 ms |
25212 KB |
Output is correct |
39 |
Correct |
16 ms |
25180 KB |
Output is correct |
40 |
Correct |
16 ms |
25180 KB |
Output is correct |
41 |
Correct |
16 ms |
25176 KB |
Output is correct |
42 |
Correct |
16 ms |
25216 KB |
Output is correct |
43 |
Correct |
16 ms |
25180 KB |
Output is correct |
44 |
Correct |
16 ms |
25180 KB |
Output is correct |
45 |
Correct |
16 ms |
25180 KB |
Output is correct |
46 |
Correct |
16 ms |
25180 KB |
Output is correct |
47 |
Correct |
16 ms |
25212 KB |
Output is correct |
48 |
Correct |
16 ms |
25224 KB |
Output is correct |
49 |
Correct |
0 ms |
344 KB |
Output is correct |
50 |
Correct |
16 ms |
25180 KB |
Output is correct |
51 |
Correct |
16 ms |
25180 KB |
Output is correct |
52 |
Correct |
16 ms |
25180 KB |
Output is correct |
53 |
Incorrect |
16 ms |
25216 KB |
Output isn't correct |
54 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
93 ms |
45500 KB |
Output is correct |
2 |
Correct |
96 ms |
46292 KB |
Output is correct |
3 |
Correct |
93 ms |
45504 KB |
Output is correct |
4 |
Correct |
94 ms |
45988 KB |
Output is correct |
5 |
Incorrect |
87 ms |
43284 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |