#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const ll Base=10007, Mod=1000000009;
const int MAXN=2000010, LOG=20;
typedef pair<ll, int> Hash;
int n, m, k, u, v, x, y, t, a, b, ans;
ll tav[MAXN];
Hash H[MAXN];
string S;
map<Hash, int> mp;
Hash operator +(Hash x, Hash y){
Hash res;
res.second=x.second+y.second;
res.first=(x.first*tav[y.second] + y.first)%Mod;
return res;
}
Hash operator -(Hash x, Hash y){
Hash res;
res.second=x.second-y.second;
res.first=(x.first-tav[res.second]*y.first)%Mod;
if (res.first<0) res.first+=Mod;
return res;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
tav[0]=1;
for (int i=1; i<MAXN; i++) tav[i]=tav[i-1]*Base%Mod;
cin>>n>>S;
if (n%2==0) kill("NOT POSSIBLE")
m=n>>1;
S="#"+S;
for (int i=1; i<=n; i++) H[i]=H[i-1]+Hash(S[i], 1);
for (int i=1; i<=m; i++){
Hash l=H[i-1]+(H[m+1]-H[i]), r=H[n]-H[m+1];
if (l!=r) continue ;
mp[l]=i;
}
for (int i=m+1; i<=n; i++){
Hash l=H[m], r=(H[i-1]-H[m])+(H[n]-H[i]);
if (l!=r) continue ;
mp[l]=i;
}
if (mp.size()>1) kill("NOT UNIQUE")
if (mp.empty()) kill("NOT POSSIBLE")
ans=(mp.begin()->second);
for (int i=1; i<=n; i++){
if (i==ans) continue ;
cout<<S[i];
if ((--m)==0) break ;
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
15992 KB |
Output is correct |
2 |
Correct |
22 ms |
16000 KB |
Output is correct |
3 |
Correct |
23 ms |
16000 KB |
Output is correct |
4 |
Correct |
23 ms |
15992 KB |
Output is correct |
5 |
Correct |
23 ms |
16000 KB |
Output is correct |
6 |
Correct |
22 ms |
16000 KB |
Output is correct |
7 |
Correct |
22 ms |
16000 KB |
Output is correct |
8 |
Correct |
22 ms |
16000 KB |
Output is correct |
9 |
Correct |
23 ms |
16000 KB |
Output is correct |
10 |
Correct |
22 ms |
16000 KB |
Output is correct |
11 |
Correct |
22 ms |
16040 KB |
Output is correct |
12 |
Correct |
22 ms |
16000 KB |
Output is correct |
13 |
Correct |
24 ms |
16000 KB |
Output is correct |
14 |
Correct |
25 ms |
16000 KB |
Output is correct |
15 |
Correct |
23 ms |
16128 KB |
Output is correct |
16 |
Correct |
22 ms |
16000 KB |
Output is correct |
17 |
Correct |
22 ms |
16000 KB |
Output is correct |
18 |
Correct |
27 ms |
16000 KB |
Output is correct |
19 |
Correct |
22 ms |
16000 KB |
Output is correct |
20 |
Correct |
23 ms |
16000 KB |
Output is correct |
21 |
Correct |
22 ms |
16000 KB |
Output is correct |
22 |
Correct |
22 ms |
16000 KB |
Output is correct |
23 |
Correct |
22 ms |
16000 KB |
Output is correct |
24 |
Correct |
25 ms |
16000 KB |
Output is correct |
25 |
Correct |
22 ms |
16000 KB |
Output is correct |
26 |
Correct |
24 ms |
16000 KB |
Output is correct |
27 |
Correct |
24 ms |
16000 KB |
Output is correct |
28 |
Correct |
22 ms |
16000 KB |
Output is correct |
29 |
Correct |
23 ms |
15936 KB |
Output is correct |
30 |
Correct |
22 ms |
16000 KB |
Output is correct |
31 |
Correct |
22 ms |
16000 KB |
Output is correct |
32 |
Correct |
22 ms |
16000 KB |
Output is correct |
33 |
Correct |
23 ms |
16000 KB |
Output is correct |
34 |
Correct |
22 ms |
16048 KB |
Output is correct |
35 |
Correct |
22 ms |
16000 KB |
Output is correct |
36 |
Correct |
22 ms |
16000 KB |
Output is correct |
37 |
Correct |
24 ms |
16000 KB |
Output is correct |
38 |
Correct |
22 ms |
16128 KB |
Output is correct |
39 |
Correct |
23 ms |
16032 KB |
Output is correct |
40 |
Correct |
22 ms |
16000 KB |
Output is correct |
41 |
Correct |
22 ms |
16000 KB |
Output is correct |
42 |
Correct |
22 ms |
16000 KB |
Output is correct |
43 |
Correct |
23 ms |
16000 KB |
Output is correct |
44 |
Correct |
24 ms |
16000 KB |
Output is correct |
45 |
Correct |
23 ms |
16000 KB |
Output is correct |
46 |
Correct |
22 ms |
16000 KB |
Output is correct |
47 |
Correct |
22 ms |
16000 KB |
Output is correct |
48 |
Correct |
23 ms |
15992 KB |
Output is correct |
49 |
Correct |
24 ms |
16000 KB |
Output is correct |
50 |
Correct |
22 ms |
16000 KB |
Output is correct |
51 |
Correct |
22 ms |
16000 KB |
Output is correct |
52 |
Correct |
24 ms |
16000 KB |
Output is correct |
53 |
Correct |
24 ms |
15992 KB |
Output is correct |
54 |
Correct |
23 ms |
16028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
50416 KB |
Output is correct |
2 |
Correct |
102 ms |
52336 KB |
Output is correct |
3 |
Correct |
104 ms |
52340 KB |
Output is correct |
4 |
Correct |
110 ms |
52340 KB |
Output is correct |
5 |
Correct |
108 ms |
52460 KB |
Output is correct |
6 |
Correct |
27 ms |
20000 KB |
Output is correct |
7 |
Correct |
123 ms |
52336 KB |
Output is correct |
8 |
Correct |
72 ms |
47796 KB |
Output is correct |
9 |
Correct |
101 ms |
48692 KB |
Output is correct |
10 |
Correct |
102 ms |
48820 KB |
Output is correct |
11 |
Correct |
69 ms |
45504 KB |
Output is correct |
12 |
Correct |
22 ms |
16000 KB |
Output is correct |
13 |
Correct |
22 ms |
16000 KB |
Output is correct |
14 |
Correct |
22 ms |
16000 KB |
Output is correct |
15 |
Correct |
23 ms |
15992 KB |
Output is correct |
16 |
Correct |
23 ms |
15992 KB |
Output is correct |
17 |
Correct |
24 ms |
16128 KB |
Output is correct |
18 |
Correct |
23 ms |
16120 KB |
Output is correct |
19 |
Correct |
22 ms |
16000 KB |
Output is correct |
20 |
Correct |
24 ms |
16000 KB |
Output is correct |
21 |
Correct |
22 ms |
16000 KB |
Output is correct |
22 |
Correct |
22 ms |
15996 KB |
Output is correct |
23 |
Correct |
24 ms |
16000 KB |
Output is correct |
24 |
Correct |
22 ms |
16000 KB |
Output is correct |
25 |
Correct |
22 ms |
16000 KB |
Output is correct |
26 |
Correct |
23 ms |
16000 KB |
Output is correct |
27 |
Correct |
23 ms |
15992 KB |
Output is correct |
28 |
Correct |
22 ms |
16000 KB |
Output is correct |
29 |
Correct |
22 ms |
16000 KB |
Output is correct |
30 |
Correct |
22 ms |
16000 KB |
Output is correct |
31 |
Correct |
22 ms |
16000 KB |
Output is correct |
32 |
Correct |
23 ms |
16000 KB |
Output is correct |
33 |
Correct |
22 ms |
16000 KB |
Output is correct |
34 |
Correct |
23 ms |
16000 KB |
Output is correct |
35 |
Correct |
22 ms |
16000 KB |
Output is correct |
36 |
Correct |
24 ms |
16000 KB |
Output is correct |
37 |
Correct |
22 ms |
16000 KB |
Output is correct |
38 |
Correct |
23 ms |
16000 KB |
Output is correct |
39 |
Correct |
24 ms |
16000 KB |
Output is correct |
40 |
Correct |
23 ms |
16000 KB |
Output is correct |
41 |
Correct |
22 ms |
16000 KB |
Output is correct |
42 |
Correct |
22 ms |
16000 KB |
Output is correct |
43 |
Correct |
23 ms |
16000 KB |
Output is correct |
44 |
Correct |
23 ms |
16120 KB |
Output is correct |
45 |
Correct |
22 ms |
16000 KB |
Output is correct |
46 |
Correct |
23 ms |
16000 KB |
Output is correct |
47 |
Correct |
22 ms |
16000 KB |
Output is correct |
48 |
Correct |
22 ms |
16000 KB |
Output is correct |
49 |
Correct |
22 ms |
16000 KB |
Output is correct |
50 |
Correct |
22 ms |
16000 KB |
Output is correct |
51 |
Correct |
22 ms |
16000 KB |
Output is correct |
52 |
Correct |
22 ms |
16000 KB |
Output is correct |
53 |
Correct |
24 ms |
16000 KB |
Output is correct |
54 |
Correct |
22 ms |
16128 KB |
Output is correct |