#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#ifdef IOI
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define md 1000000007
#define all(v) v.begin(),v.end()
const int MAXN=2000001+2;
const int MOD1=1e9+7,P=37;
// #define int long long
ll binpow(int a,int b,int mod){
int res=1;
while(b){
if(b&1) res=((ll)res%mod*(ll)a%mod)%mod;
a=((ll)a%mod*(ll)a%mod)%mod;
b>>=1;
}
return res%mod;
}
ll invmod(int a,int mod){
return (ll)binpow(a,mod-2,mod)%mod;
}
int pref1[MAXN];
ll inv1[MAXN];
const int MOD2=1404543827;
const int P2=83;
int pref2[MAXN];
ll inv2[MAXN];
int sum1(int l,int r){
if(l==0) return (ll)pref1[r]%MOD1;
else
return (((ll)pref1[r]-(ll)pref1[l-1]+3LL*MOD1)%MOD1*((ll)inv1[l]%MOD1))%MOD1;
}
int sum2(int l,int r){
if(l==0) return (ll)pref2[r]%MOD2;
else
return (((ll)pref2[r]-(ll)pref2[l-1]+3LL*MOD2)%MOD2*((ll)inv2[l]%MOD2))%MOD2;
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n;
cin>>n;
string s;
cin>>s;
memset(pref1,0,sizeof(pref1));
if(n%2==0){
cout<<"NOT POSSIBLE"<<endl;
return 0;
}
inv1[0]=1;
inv1[1]=invmod(P,MOD1);
for(int i=2;i<MAXN;i++){
inv1[i]=((ll)inv1[i-1]%MOD1*((ll)inv1[1]%MOD1))%MOD1;
}
ll c=1;
for(int i=0;i<n;i++){
int x=s[i]-'A'+1;
if(i) pref1[i]=pref1[i-1];
pref1[i]%=MOD1;
pref1[i]=(pref1[i]%MOD1+((ll)x%MOD1*(ll)c%MOD1)%MOD1)%MOD1;
c=((ll)c%MOD1*P%MOD1)%MOD1;
}
inv2[0]=1;
inv2[1]=invmod(P2,MOD2);
for(int i=2;i<MAXN;i++){
inv2[i]=(inv2[i-1]%MOD2*(inv2[1]%MOD2))%MOD2;
}
c=1;
for(int i=0;i<n;i++){
int x=s[i]-'A'+1;
if(i) pref2[i]=pref2[i-1];
pref2[i]=(pref2[i]%MOD2+(x%MOD2*c%MOD2)%MOD2)%MOD2;
c=(c%MOD2*P2%MOD2)%MOD2;
}
// for(int i=0;i<n;i++){
// dbg(pref1[i],pref2[i],inv1[i],inv2[i])
// }
vector<pair<int,int>> ans;
map<ll,pair<int,int>> mp;
for(int i=0;i<n;i++){
int l1=0,r1=0,l2=0,r2=n-1;
if(i==0){
l1=1;
}
if(i==n-1){
r2=n-2;
}
r1=l1+(n-2)/2;
if(i>0&&i<=r1) r1++;
l2=r2-(n-2)/2;
if(i!=n-1&&i>=l2) l2--;
if((i>r1&&i<l2)||i==0||i==n-1){
if((ll)sum1(l1,r1)==(ll)sum1(l2,r2)&&(ll)sum2(l1,r1)==(ll)sum2(l2,r2)) {
mp[sum1(l1,r1)]={l1,r1};
ans.pb({l1,r1});
}
else continue;
}
if(i<=r1){
int t=i-1;
int t1=i+1;
int s1=0;
s1+=sum1(l1,t)%MOD1;
s1%=MOD1;
s1+=((ll)binpow(P,(i%((n-2)/2+1)),MOD1)%MOD1*sum1(t1,r1)%MOD1)%MOD1;
s1%=MOD1;
s1+=MOD1;
s1%=MOD1;
int s2=0;
s2+=sum2(l1,t)%MOD2;
s2%=MOD2;
s2+=(binpow(P2,(i%((n-2)/2+1)),MOD2)%MOD2*sum2(t1,r1)%MOD2)%MOD2;
s2%=MOD2;
s2+=MOD2;
s2%=MOD2;
if(s1==sum1(l2,r2)%MOD1&&s2==sum2(l2,r2)%MOD2){
ans.pb({l2,r2});
mp[s1]={l2,r2};
}
}else{
int t=i-1;
int t1=i+1;
int s1=0;
s1+=sum1(l2,t)%MOD1;
s1%=MOD1;
s1+=(binpow(P,(i%((n-2)/2+1)),MOD1)%MOD1*sum1(t1,r2)%MOD1)%MOD1;
s1%=MOD1;
s1+=MOD1;
s1%=MOD1;
int s2=0;
s2+=sum2(l2,t)%MOD2;
s2%=MOD2;
s2+=(binpow(P2,(i%((n-2)/2+1)),MOD2)%MOD2*sum2(t1,r2)%MOD2)%MOD2;
s2%=MOD2;
s2+=MOD2;
s2%=MOD2;
// dbg(i,s1,s2,sum1(l1,r1),sum2(l1,r1))
// dbg(s2,sum2(l1,r1))
if(s1==sum1(l1,r1)&&s2==sum2(l1,r1)%MOD2) {
ans.pb({l1,r1});
mp[s1]={l1,r1};
}
}
}
// dbg("done")
if(mp.size()==1){
pair<int,int> anss=mp.begin()->second;
cout<<s.substr(anss.F,anss.S-anss.F+1)<<endl;
}else{
if(mp.empty()){
cout<<"NOT POSSIBLE"<<endl;
return 0;
}
cout<<"NOT UNIQUE"<<endl;
return 0;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
41044 KB |
Output is correct |
2 |
Correct |
23 ms |
41052 KB |
Output is correct |
3 |
Correct |
23 ms |
41048 KB |
Output is correct |
4 |
Correct |
22 ms |
41048 KB |
Output is correct |
5 |
Correct |
24 ms |
40992 KB |
Output is correct |
6 |
Correct |
22 ms |
41044 KB |
Output is correct |
7 |
Correct |
22 ms |
40996 KB |
Output is correct |
8 |
Correct |
22 ms |
41052 KB |
Output is correct |
9 |
Correct |
24 ms |
41052 KB |
Output is correct |
10 |
Correct |
24 ms |
41048 KB |
Output is correct |
11 |
Correct |
22 ms |
41304 KB |
Output is correct |
12 |
Correct |
22 ms |
41044 KB |
Output is correct |
13 |
Correct |
22 ms |
41044 KB |
Output is correct |
14 |
Correct |
22 ms |
41052 KB |
Output is correct |
15 |
Correct |
22 ms |
40988 KB |
Output is correct |
16 |
Correct |
22 ms |
41044 KB |
Output is correct |
17 |
Correct |
22 ms |
41040 KB |
Output is correct |
18 |
Correct |
23 ms |
41044 KB |
Output is correct |
19 |
Correct |
22 ms |
41052 KB |
Output is correct |
20 |
Correct |
22 ms |
41052 KB |
Output is correct |
21 |
Correct |
22 ms |
41052 KB |
Output is correct |
22 |
Correct |
22 ms |
41048 KB |
Output is correct |
23 |
Correct |
23 ms |
41040 KB |
Output is correct |
24 |
Correct |
2 ms |
10072 KB |
Output is correct |
25 |
Correct |
2 ms |
10332 KB |
Output is correct |
26 |
Correct |
3 ms |
10188 KB |
Output is correct |
27 |
Correct |
22 ms |
41040 KB |
Output is correct |
28 |
Correct |
22 ms |
41232 KB |
Output is correct |
29 |
Correct |
22 ms |
41064 KB |
Output is correct |
30 |
Correct |
23 ms |
41300 KB |
Output is correct |
31 |
Correct |
22 ms |
41060 KB |
Output is correct |
32 |
Correct |
22 ms |
41248 KB |
Output is correct |
33 |
Correct |
22 ms |
41256 KB |
Output is correct |
34 |
Correct |
22 ms |
41044 KB |
Output is correct |
35 |
Correct |
22 ms |
41052 KB |
Output is correct |
36 |
Correct |
22 ms |
41040 KB |
Output is correct |
37 |
Correct |
22 ms |
41052 KB |
Output is correct |
38 |
Correct |
22 ms |
41248 KB |
Output is correct |
39 |
Correct |
22 ms |
41052 KB |
Output is correct |
40 |
Correct |
22 ms |
41040 KB |
Output is correct |
41 |
Correct |
22 ms |
41052 KB |
Output is correct |
42 |
Correct |
22 ms |
41044 KB |
Output is correct |
43 |
Correct |
22 ms |
41052 KB |
Output is correct |
44 |
Incorrect |
22 ms |
41052 KB |
Output isn't correct |
45 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
808 ms |
49280 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |