#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
const ll mod = 1e9 + 7,inf = 1e18,p = 31;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n = 2e6 + 5;
vi a(n);
vl hsh(n,1),power(n,1);
ll poww(ll a,ll b)
{
if (b == 0)return 1;
if (b == 1)return a;
ll ret = poww(a,b/2);
if (b%2 == 0)return (ret * ret)%mod;
return ((ret * ret)%mod * a)%mod;
}
ll inv(ll a)
{
return (poww(a,mod - 2)%mod + mod)%mod;
}
ll get_hash(int a,int b)
{
return (((hsh[b] - ((a >= 1 ? hsh[a - 1] : 0))%mod))%mod + mod)%mod;
}
int main()
{
for (int i = 1;i<=n;i++)power[i] = (power[i - 1] * p)%mod;
cin>>n;
if (n % 2 == 0){cout<<"NOT POSSIBLE";return 0;}
string s;
cin>>s;
for (int i = 0;i<n;i++)
a[i] = s[i] - 'A' + 1;
hsh[0] = a[0];
set<int>vals;
for (int i = 0;i<n - 1;i++)
hsh[i + 1] = (poww(p,i + 1) * a[i + 1] + hsh[i])%mod;
int cnt = 0,start = -1,len = (n - 1)/2;
for (int i = 0;i<n;i++){
if (i == 0){
ll v1 = ((hsh[len] - hsh[0])%mod + mod)%mod;
ll v2 = ((hsh[n - 1] - hsh[len])%mod + mod)%mod;
if ((v1 * power[len])%mod == v2){
vals.insert((v1 * inv(p))%mod);
cnt++,start = 1;
}
}
else if (i < len){
ll v1 = ((((hsh[i - 1] * p)%mod + (hsh[len] - hsh[i]))%mod)%mod + mod)%mod;
ll v2 = ((hsh[n - 1] - hsh[len])%mod + mod)%mod;
if ((v1 * power[len])%mod == v2){
vals.insert((v1 * inv(p))%mod);
start = len + 1;
}
}
else{
ll v1 = hsh[len - 1];
ll v2 = ((((hsh[i - 1] - hsh[len - 1]) * p)%mod + (hsh[n - 1] - hsh[i])%mod)%mod + mod)%mod;
if ((v1 * power[len + 1])%mod == v2){
vals.insert(v1);
start = 0;
}
}
}
cnt = vals.size();
if (cnt > 1)cout<<"NOT UNIQUE";
else if (cnt == 0)cout<<"NOT POSSIBLE";
else cout<<s.substr(start,len);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
39372 KB |
Output is correct |
2 |
Correct |
35 ms |
39372 KB |
Output is correct |
3 |
Correct |
35 ms |
39424 KB |
Output is correct |
4 |
Correct |
39 ms |
39424 KB |
Output is correct |
5 |
Correct |
35 ms |
39408 KB |
Output is correct |
6 |
Correct |
34 ms |
39372 KB |
Output is correct |
7 |
Correct |
35 ms |
39372 KB |
Output is correct |
8 |
Correct |
34 ms |
39372 KB |
Output is correct |
9 |
Correct |
35 ms |
39440 KB |
Output is correct |
10 |
Correct |
35 ms |
39444 KB |
Output is correct |
11 |
Correct |
36 ms |
39372 KB |
Output is correct |
12 |
Correct |
34 ms |
39396 KB |
Output is correct |
13 |
Correct |
34 ms |
39452 KB |
Output is correct |
14 |
Correct |
34 ms |
39356 KB |
Output is correct |
15 |
Correct |
35 ms |
39344 KB |
Output is correct |
16 |
Correct |
35 ms |
39372 KB |
Output is correct |
17 |
Correct |
36 ms |
39492 KB |
Output is correct |
18 |
Correct |
35 ms |
39372 KB |
Output is correct |
19 |
Correct |
35 ms |
39448 KB |
Output is correct |
20 |
Correct |
34 ms |
39404 KB |
Output is correct |
21 |
Correct |
35 ms |
39448 KB |
Output is correct |
22 |
Correct |
35 ms |
39364 KB |
Output is correct |
23 |
Correct |
34 ms |
39372 KB |
Output is correct |
24 |
Correct |
35 ms |
39412 KB |
Output is correct |
25 |
Correct |
35 ms |
39452 KB |
Output is correct |
26 |
Correct |
36 ms |
39372 KB |
Output is correct |
27 |
Correct |
35 ms |
39424 KB |
Output is correct |
28 |
Correct |
38 ms |
39372 KB |
Output is correct |
29 |
Correct |
35 ms |
39436 KB |
Output is correct |
30 |
Correct |
39 ms |
39432 KB |
Output is correct |
31 |
Correct |
35 ms |
39372 KB |
Output is correct |
32 |
Correct |
35 ms |
39372 KB |
Output is correct |
33 |
Correct |
39 ms |
39500 KB |
Output is correct |
34 |
Correct |
35 ms |
39456 KB |
Output is correct |
35 |
Correct |
35 ms |
39372 KB |
Output is correct |
36 |
Correct |
36 ms |
39372 KB |
Output is correct |
37 |
Correct |
35 ms |
39372 KB |
Output is correct |
38 |
Correct |
35 ms |
39324 KB |
Output is correct |
39 |
Correct |
34 ms |
39372 KB |
Output is correct |
40 |
Correct |
35 ms |
39372 KB |
Output is correct |
41 |
Correct |
35 ms |
39384 KB |
Output is correct |
42 |
Correct |
35 ms |
39376 KB |
Output is correct |
43 |
Correct |
35 ms |
39492 KB |
Output is correct |
44 |
Correct |
35 ms |
39440 KB |
Output is correct |
45 |
Correct |
36 ms |
39320 KB |
Output is correct |
46 |
Correct |
36 ms |
39372 KB |
Output is correct |
47 |
Correct |
35 ms |
39372 KB |
Output is correct |
48 |
Correct |
34 ms |
39436 KB |
Output is correct |
49 |
Correct |
34 ms |
39376 KB |
Output is correct |
50 |
Correct |
36 ms |
39372 KB |
Output is correct |
51 |
Correct |
36 ms |
39436 KB |
Output is correct |
52 |
Correct |
36 ms |
39364 KB |
Output is correct |
53 |
Correct |
35 ms |
39396 KB |
Output is correct |
54 |
Correct |
35 ms |
39448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
456 ms |
43556 KB |
Output is correct |
2 |
Correct |
458 ms |
43536 KB |
Output is correct |
3 |
Correct |
459 ms |
43452 KB |
Output is correct |
4 |
Correct |
454 ms |
43572 KB |
Output is correct |
5 |
Correct |
478 ms |
43496 KB |
Output is correct |
6 |
Correct |
36 ms |
39372 KB |
Output is correct |
7 |
Execution timed out |
763 ms |
45304 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |