#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = int(2e5)+5, MOD = int(1e9)+7, charsz = 29;
int n;
string S;
pair<int, int> st[4*maxn+10];
int modpow(int a, int b)
{
if(!b) return 1;
else
{
int res = modpow(a, b/2);
res *= res;
res %= MOD;
if(b%2) res *= a%MOD;
return res%MOD;
}
}
pair<int, int> combine(pair<int, int> a, pair<int, int> b)
{
pair<int, int> res = {a.first, a.second+b.second};
res.first += (b.first%MOD*modpow(charsz, a.second)%MOD)%MOD;
res.first %= MOD;
return res;
}
inline int left(int node) { return (node<<1); }
inline int right(int node) { return (node<<1)+1; }
void build(int node, int L, int R)
{
if(L == R) st[node] = {int(S[L]-'A'), 1};
else
{
build(left(node), L, (L+R)/2);
build(right(node), (L+R)/2+1, R);
st[node] = combine(st[left(node)], st[right(node)]);
}
}
pair<int, int> qry(int node, int L, int R, int a, int b)
{
if(a > R || b < L) return {0, 0};
else if(a <= L && R <= b) return st[node];
else return combine(qry(left(node), L, (L+R)/2, a, b), qry(right(node), (L+R)/2+1, R, a, b));
}
int main(void)
{
scanf("%d", &n);
cin >> S;
build(1, 0, n-1);
vector<int> ans;
for(int i = 0;i < n;i++)
{
pair<int, int> h1, h2;
if(i < n/2)
{
h1 = combine(qry(1, 0, n-1, 0, i-1), qry(1, 0, n-1, i+1, n/2));
h2 = qry(1, 0, n-1, n/2+1, n-1);
}
else
{
h1 = qry(1, 0, n-1, 0, n/2-1);
h2 = combine(qry(1, 0, n-1, n/2, i-1), qry(1, 0, n-1, i+1, n-1));
}
//cout << i << " " << h1.first << " " << h1.second << " " << h2.first << " " << h2.second << "\n";
if(h1 == h2) ans.push_back(i);
}
if(ans.empty()) printf("NOT POSSIBLE\n");
else if(int(ans.size()) > 1) printf("NOT UNIQUE\n");
else
{
if(ans[0] < n/2) cout << S.substr(n/2+1, ans[0]+1) << "\n";
else cout << S.substr(0, ans[0]+1) << "\n";
}
}
Compilation message
friends.cpp: In function 'int main()':
friends.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
76 ms |
6620 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
