#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef string str;
typedef vector<ll> vint;
const ll MOD1 = 1999998893;
const ll MOD2 = 2100003611;
const ll BASE = 29;
const char STARTING_LETTER = 'A';
ll hashChar(char c) {
return c - STARTING_LETTER + 1;
}
pair<ll, ll> hashStr(pair<ll, ll> prevHash, char curChar) {
return {((prevHash.first * BASE) % MOD1 + hashChar(curChar)) % MOD1,
((prevHash.second * BASE) % MOD2 + hashChar(curChar)) % MOD2};
}
class RollingHash {
private:
ll mod1, mod2, base;
vector<ll> powOfBase1, powOfBase2;
public:
RollingHash(ll mod1, ll mod2, ll base) : mod1(mod1), mod2(mod2), base(base) {}
void calculatePowers(int n) {
powOfBase1.resize(n);
powOfBase2.resize(n);
powOfBase1[0] = 1;
powOfBase2[0] = 1;
for (int i = 1; i < n; i++) {
powOfBase1[i] = (base * powOfBase1[i - 1]) % mod1;
powOfBase2[i] = (base * powOfBase2[i - 1]) % mod2;
}
}
pair<ll, ll> hashString(const str& s) {
pair<ll, ll> hashValue = {0, 0};
for (char c : s) {
hashValue = hashStr(hashValue, c);
}
return hashValue;
}
pair<ll, ll> updateHash(pair<ll, ll> prevHash, char oldChar, char newChar, int length) {
pair<ll, ll> newHash = prevHash;
ll pow1 = powOfBase1[length - 1];
ll pow2 = powOfBase2[length - 1];
newHash.first = ((newHash.first - (pow1 * hashChar(oldChar)) % mod1 + mod1) * base + hashChar(newChar)) % mod1;
newHash.second = ((newHash.second - (pow2 * hashChar(oldChar)) % mod2 + mod2) * base + hashChar(newChar)) % mod2;
return newHash;
}
};
str findUniqueString(int n, const str& u) {
str left = u.substr(0, n / 2 + 1);
str right = u.substr(n / 2 + 1);
str ans = "";
pair<ll, ll> ansHash = {0, 0};
RollingHash rollingHash(MOD1, MOD2, BASE);
rollingHash.calculatePowers(n);
pair<ll, ll> leftHash = rollingHash.hashString(left);
pair<ll, ll> rightHash = rollingHash.hashString(right);
for (int i = 0; i < left.size(); i++) {
pair<ll, ll> newRightHash = rightHash;
if (i > 0) {
char oldChar = right[i - 1];
char newChar = left[i - 1];
newRightHash = rollingHash.updateHash(rightHash, oldChar, newChar, right.size());
}
if (leftHash == newRightHash) {
for (int j = 0; j < left.size(); j++) {
if (i != j) ans += left[j];
}
ansHash = rollingHash.hashString(ans);
if (!ans.empty() && ansHash != leftHash) return "NOT UNIQUE";
}
}
if (ans.empty()) return "NOT POSSIBLE";
return ans;
}
int main() {
srand(time(0));
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cout << fixed << setprecision(15);
int n;
cin >> n;
str u;
cin >> u;
str result = findUniqueString(n, u);
cout << result;
return 0;
}
Compilation message
friends.cpp: In function 'str findUniqueString(int, const str&)':
friends.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i = 0; i < left.size(); i++) {
| ~~^~~~~~~~~~~~~
friends.cpp:86:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int j = 0; j < left.size(); j++) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
74 ms |
35676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
