This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod = 2000002133;
ll mul(ll a, ll b){
return ((a % mod) * (b % mod)) % mod;
}
ll add(ll a, ll b){
return (a + b) % mod;
}
ll sub(ll a, ll b){
return (a + mod - b) % mod;
}
ll binexp(ll a, ll b){
if(!b)
return 1;
ll ret = 1;
while(b){
if(b & 1)
ret = mul(ret, a);
b>>=1;
a = mul(a, a);
}
return ret;
}
ll modinv(ll a){
return binexp(a, mod - 2);
}
#define val(pre, l, r) mul(l == 0 ? pre[r] : sub(pre[r], pre[l - 1]), inv[l])
#define combine(hash1, hash2, v) add(mul(hash2, v), hash1)
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,cnt=0;
string s;
cin>>n>>s;
if(n == 1 || n % 2 == 0){
return cout<<"NOT POSSIBLE", 0;
}
ll p = 47, pw = 1;
ll hash[n],inv[n],c[n];
inv[0]=1;
inv[1] = modinv(p);
for(int i = 0; i < n; i++){
c[i] = pw;
hash[i] = mul(s[i] - 'A' + 1, pw);
if(i)hash[i] = add(hash[i], hash[i - 1]);
pw=mul(pw,p);
if(i >= 2)inv[i]=mul(inv[1],inv[i-1]);
}
int l = -1, r = -1, rev = 0;
for(int i = 0; i < n / 2; i++){
ll val1,val2=val(hash, n / 2 + 1, n - 1);
if(i == 0){
val1 = val(hash, i + 1, n / 2);
}else{
val1 = combine(val(hash, 0, i - 1), val(hash, i + 1, n / 2), c[i]);
}
if(val1==val2){
l = n / 2 + 1, r = n - 1;
++cnt;
}
}
if(val(hash, 0, n / 2 - 1) == val(hash, n / 2 + 1, n - 1))++cnt, l = 0, r = n / 2 - 1;
reverse(s.begin(), s.end());
inv[0]=1;
inv[1] = modinv(p);
pw=1;
for(int i = 0; i < n; i++){
c[i] = pw;
hash[i] = mul(s[i] - 'A' + 1, pw);
if(i)hash[i] = add(hash[i], hash[i - 1]);
pw=mul(pw,p);
if(i >= 2)inv[i]=mul(inv[1],inv[i-1]);
}
for(int i = 0; i < n / 2; i++){
ll val1,val2=val(hash, n / 2 + 1, n - 1);
if(i == 0){
val1 = val(hash, i + 1, n / 2);
}else{
val1 = combine(val(hash, 0, i - 1), val(hash, i + 1, n / 2), c[i]);
}
if(val1==val2){
l = n / 2 + 1, r = n - 1, rev = 1;
++cnt;
}
}
if(cnt == 0){
cout<<"NOT POSSIBLE";
}
else if(cnt == 1){
if(!rev){
reverse(s.begin(),s.end());
for(int i = l; i <= r; i++)cout<<s[i];
}
else{
for(int i = r; i >= l; i--)cout<<s[i];
}
}
else{
cout<<"NOT UNIQUE";
}
return 0;
}
Compilation message (stderr)
friends.cpp: In function 'int main()':
friends.cpp:29:42: warning: array subscript -3 is below array bounds of 'll [(<anonymous> + 1)]' {aka 'long long int [(<anonymous> + 1)]'} [-Warray-bounds]
29 | #define val(pre, l, r) mul(l == 0 ? pre[r] : sub(pre[r], pre[l - 1]), inv[l])
| ^
friends.cpp:53:22: note: in expansion of macro 'val'
53 | ll val1,val2=val(hash, n / 2 + 1, n - 1);
| ^~~
friends.cpp:29:42: warning: array subscript -3 is below array bounds of 'll [(<anonymous> + 1)]' {aka 'long long int [(<anonymous> + 1)]'} [-Warray-bounds]
29 | #define val(pre, l, r) mul(l == 0 ? pre[r] : sub(pre[r], pre[l - 1]), inv[l])
| ^
friends.cpp:64:35: note: in expansion of macro 'val'
64 | if(val(hash, 0, n / 2 - 1) == val(hash, n / 2 + 1, n - 1))++cnt, l = 0, r = n / 2 - 1;
| ^~~
friends.cpp:29:42: warning: array subscript -3 is below array bounds of 'll [(<anonymous> + 1)]' {aka 'long long int [(<anonymous> + 1)]'} [-Warray-bounds]
29 | #define val(pre, l, r) mul(l == 0 ? pre[r] : sub(pre[r], pre[l - 1]), inv[l])
| ^
friends.cpp:77:22: note: in expansion of macro 'val'
77 | ll val1,val2=val(hash, n / 2 + 1, n - 1);
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |