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;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
const int nax = (int)2000002;
int n, p = 31, m = (int) 461323;
ll hsh[nax];
string s;
ll bpow(ll u, ll b){
ll res = 1;
while(b){
if (b & 1)res = (res * u)%m;
b/=2;
u = (u * u)%m;
}
return res;
}
ll inv(ll p){
return bpow(p,m-2);
}
ll ips[nax + 1];
ll ps[nax+1];
void solve(){
cin >> n >> s;
if (n % 2 == 0){
cout << "NOT POSSIBLE" << endl;
return;
}
for (int i = 0; i < n; i++){
hsh[i] = (s[i] - 'A' + 1) * ps[i] % m;
if (i)hsh[i] += hsh[i - 1];
hsh[i]%=m;
}
//cout << hsh[0] << endl;
//cout << ps[3] << endl;
int L1[n], R1[n], L2[n], R2[n];
unordered_set<ll>se;
string res = "";
for(int i = 0; i < n; i++){
L1[i] = 0;
if (i == 0)L1[i]++;
R1[i] = L1[i] + n / 2 - 1;
if (R1[i] >= i && L1[i] < i)R1[i]++;
ll hash1 = 0;
if (R1[i] > i && L1[i] < i){
hash1 = (i < 1 ? 0 : hsh[i - 1]);
hash1 += (((hsh[R1[i]] - hsh[i] + m)%m) * ips[i + 1]%m)
* ps[i] % m;
hash1 %= m;
}else{
hash1 = hsh[R1[i]];
if (L1[i]){
hash1 -= hsh[L1[i] - 1];
hash1+=m;
hash1 %= m;
hash1 *= ips[L1[i]];
}
hash1 %= m;
}
L2[i] = R1[i] + 1;
if (L2[i] == i)++L2[i];
R2[i] = L2[i] + n / 2 - 1;
ll hash2 = 0;
if (R2[i] >= i && L2[i] < i)++R2[i];
//cout << L1[i] << " " << R1[i] << " " << L2[i] << " " << R2[i] << endl;
if (L2[i] > i){
hash2 = (m + hsh[R2[i]] - hsh[L2[i] - 1])%m;
hash2 *= ips[L2[i]];
hash2 %= m;
}else{
hash2 = (hsh[i - 1] - hsh[L2[i] - 1] + m)%m;
hash2 *= ips[L2[i]];
hash2 %= m;
ll hash3 = (m + hsh[R2[i]] - hsh[i])%m;
hash3 *= ips[i+1];
hash3 %= m;
hash3 *= ps[i - L2[i]];
hash3 %= m;
//if (i == 5)cout << hash3 << endl;
if (i - 1 != R2[i]) hash2 += hash3;
hash2 %= m;
}
if (hash1 == hash2){
if (se.empty()){
for (int j = 0; j < n; j++){
if (i == j)continue;
if (res.size() < n / 2)res += s[j];
else break;
}
}
se.insert(hash1);
if (se.size() > 1){
cout << "NOT UNIQUE" << endl;
return;
}
}
}
if (se.empty())cout << "NOT POSSIBLE" << endl;
else cout << res << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt = 1;
ps[0] = 1;
for (int i = 1; i < nax; i++){
ps[i] = p;
ps[i] *= ps[i - 1];
ps[i] %= m;
}
for (int i = 0; i < nax; i++){
ips[i] = inv(ps[i]);
}
//cin >> tt;
while(tt--){
solve();
}
return 0;
}
Compilation message (stderr)
friends.cpp: In function 'void solve()':
friends.cpp:132:25: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
132 | if (res.size() < n / 2)res += s[j];
| ~~~~~~~~~~~^~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |