/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
/**
Solution:
1. It's obvious that T totally depends on S, which means I can determine S by converting U to T.
2. I can convert U to possible T by removing only one letter from any position and check if it's correct.
3. To quickly check if possible T can be done by copying, I can compare first and second half of it.
And to quickly compare first and second half of it, I can use polynomial hashing property that:
hash(S[l : r]) = (hash(S[1 : r]) - hash(S[1 : l - 1]) * (base ^ (r - l + 1)) + mod) % mod.
Since r - l + 1 <= n, then base ^ (r - l + 1) can be precalculated.
5. If strings are equal (hashes are also equal), then I check answer.
If it's empty, then I fill it and calculate its hash.
Else I compare answer's hash and resulting string hash (both are already calculated).
If they differ, then answer is "NO UNIQUE". Otherwise, nothing is changed.
Time complexity: O(n).
**/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
#define int long long
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0 //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt" : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
void read() {} template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg) ;read(args...) ;}
void print(){} template<typename Arg,typename... Args> void print(Arg arg,Args... args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg arg,Args... args){put (arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here
const long long mod1 = 1999998893;
const long long mod2 = 2100003611;
const long long base = 29;
const char startingLetter = 'A'; //starting letter of the alphabet
long long hashChar(char c){
return c - startingLetter + 1;
}
pair<long long, long long> hashStr(pair<long long, long long> prevHash, char curChar) {
return {((prevHash.first * base) % mod1 + hashChar(curChar)) % mod1,
((prevHash.second * base) % mod2 + hashChar(curChar)) % mod2};
}
const int N = 2e6 + 1;
int powOfBase1[N], powOfBase2[N];
void run() {
int n;
get n;
str u;
get u;
powOfBase1[0] = 1;
powOfBase2[0] = 1;
rep(i, 1, n + 1) {
powOfBase1[i] = (base * powOfBase1[i - 1]) % mod1;
powOfBase2[i] = (base * powOfBase2[i - 1]) % mod2;
}
str left = "", right = "";
rep(i, 0, n / 2 + 1)
left += u[i];
rep(i, n / 2 + 1, n)
right += u[i];
str ans = "";
pair<int, int> ansHsh = {0, 0};
rep(z, 0, 2) {
v<pair<int, int>> hshLeft, hshRight;
hshLeft.pb({hashChar(left[0]), hashChar(left[0])});
rep(i, 1, sz(left)) {
auto d = hshLeft.back();
hshLeft.pb(hashStr(d, left[i]));
}
hshRight.pb({hashChar(right[0]), hashChar(right[0])});
rep(i, 1, sz(right)) {
auto d = hshRight.back();
hshRight.pb(hashStr(d, right[i]));
}
if (z) {
//debug(sz(hshRight), right, sz(hshLeft), left);
rep(i, 1, sz(right)) {
auto resultHash = hshRight.back();
int offset = sz(right) - (i + 1);
resultHash.first =
((resultHash.first - (powOfBase1[offset] * hshRight[i].first) % mod1) % mod1 + mod1) % mod1;
if (i)
resultHash.first = (resultHash.first + (powOfBase1[offset] * hshRight[i - 1].first) % mod1) % mod1;
resultHash.second =
((resultHash.second - (powOfBase2[offset] * hshRight[i].second) % mod2) % mod2 + mod2) % mod2;
if (i)
resultHash.second = (resultHash.second + (powOfBase2[offset] * hshRight[i - 1].second) % mod2) % mod2;
if (resultHash == hshLeft.back()) {
if (ans == "") {
rep(j, 0, sz(right))
if (i != j)
ans += right[j];
for (char j : ans)
ansHsh = hashStr(ansHsh, j);
} else {
if (resultHash != ansHsh) {
put "NOT UNIQUE";
return;
}
}
}
}
} else {
rep(i, 0, sz(left)) {
auto resultHash = hshLeft.back();
int offset = sz(left) - (i + 1);
resultHash.first =
((resultHash.first - (powOfBase1[offset] * hshLeft[i].first) % mod1) % mod1 + mod1) % mod1;
if (i)
resultHash.first = (resultHash.first + (powOfBase1[offset] * hshLeft[i - 1].first) % mod1) % mod1;
resultHash.second =
((resultHash.second - (powOfBase2[offset] * hshLeft[i].second) % mod2) % mod2 + mod2) % mod2;
if (i)
resultHash.second = (resultHash.second + (powOfBase2[offset] * hshLeft[i - 1].second) % mod2) % mod2;
if (resultHash == hshRight.back()) {
if (ans == "") {
rep(j, 0, sz(left))
if (i != j)
ans += left[j];
for (char j : ans)
ansHsh = hashStr(ansHsh, j);
} else {
if (resultHash != ansHsh) {
put "NOT UNIQUE";
return;
}
}
}
}
}
if (z)
break;
right = left.back() + right;
left.pop_back();
}
//debug(ans[0]);
if (sz(ans) == 0)
put "NOT POSSIBLE";
else
put ans;
}
int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2400 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 22 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2548 KB |
Output is correct |
| 27 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 30 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 32 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 33 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 34 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 35 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 37 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 38 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 39 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 40 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 41 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 42 |
Correct |
1 ms |
2476 KB |
Output is correct |
| 43 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 44 |
Correct |
2 ms |
2392 KB |
Output is correct |
| 45 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 46 |
Correct |
1 ms |
2444 KB |
Output is correct |
| 47 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 48 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 49 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 50 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 51 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 52 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 53 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 54 |
Correct |
1 ms |
2392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
85068 KB |
Output is correct |
| 2 |
Correct |
143 ms |
84948 KB |
Output is correct |
| 3 |
Correct |
142 ms |
84992 KB |
Output is correct |
| 4 |
Correct |
143 ms |
84808 KB |
Output is correct |
| 5 |
Correct |
143 ms |
86344 KB |
Output is correct |
| 6 |
Correct |
132 ms |
83280 KB |
Output is correct |
| 7 |
Correct |
162 ms |
85064 KB |
Output is correct |
| 8 |
Correct |
125 ms |
83612 KB |
Output is correct |
| 9 |
Correct |
131 ms |
82872 KB |
Output is correct |
| 10 |
Correct |
124 ms |
85536 KB |
Output is correct |
| 11 |
Correct |
116 ms |
79320 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
1 ms |
2516 KB |
Output is correct |
| 22 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 23 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 24 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 26 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 30 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 32 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 33 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 34 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 35 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 36 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 37 |
Correct |
1 ms |
2520 KB |
Output is correct |
| 38 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 39 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 40 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 41 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 42 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 43 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 44 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 45 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 46 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 47 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 48 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 49 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 50 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 51 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 52 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 53 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 54 |
Correct |
1 ms |
2396 KB |
Output is correct |
