Submission #987559

#TimeUsernameProblemLanguageResultExecution timeMemory
987559AiperiiiThree Friends (BOI14_friends)C++14
0 / 100
120 ms35636 KiB
#include <bits/stdc++.h> #define int long long #define ff first #define ss second #define pb push_back #define all(x) x.begin(),x.end() using namespace std; const int N=2e6+5,t=33,mod=1e9+7; int pw[N],p[N]; char s[N]; bool ok(int l1,int r1,int l2,int r2){ if(l1>r1)return 1; int h1=(p[r1]-(p[l1-1]*pw[r1-l1+1])); if(h1<0)h1+=(abs(h1)/mod+1)*mod; h1%=mod; int h2=(p[r2]-(p[l2-1]*pw[r2-l2+1])); if(h2<0)h2+=(abs(h2)/mod+1)*mod; h2%=mod; if(h1==h2)return 1; return 0; } signed main(){ ios_base::sync_with_stdio(); cin.tie(0);cout.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ cin>>s[i]; } if(n%2==0){ cout<<"NOT POSSIBLE\n"; return 0; } pw[0]=1; for(int i=1;i<=n;i++){ pw[i]=pw[i-1]*t%mod; p[i]=p[i-1]*t+s[i]%mod; } int p1=0,p2=0; for(int i=1;i<=n;i++){ bool ok1=1,ok2=1; if(i<=n/2+1){ if(i!=1)ok1=ok(1,i-1,n/2+2,n/2+i); if(i!=n/2+1)ok2=ok(i+1,n/2+1,n/2+i+1,n); if(ok1 && ok2 && p1==0)p1=1; } else{ ok1=ok(1,1+(i-1-(n/2+1)),n/2+1,i-1); if(i!=n)ok2=ok(n/2-n+i+1,n/2,i+1,n); if(ok1 && ok2 && p2==0)p2=1; } } //cout<<p1<<" "<<p2<<"\n"; if(p1==0 && p2==0)cout<<"NOT POSSIBLE\n"; else if(p2==0 or ok(1,n/2,n/2+2,n)){ for(int i=n/2+2;i<=n;i++)cout<<s[i]; cout<<"\n"; } else if(p1==0){ for(int i=1;i<=n/2;i++)cout<<s[i]; cout<<"\n"; } else cout<<"NOT UNIQUE\n"; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...