Submission #938201

#TimeUsernameProblemLanguageResultExecution timeMemory
938201Faisal_SaqibThree Friends (BOI14_friends)C++17
0 / 100
30 ms8140 KiB
#include <iostream> #include <set> using namespace std; #define ll long long const ll N=10000; ll pre[N],pw[N],base=717,mod=1e9+9; ll pre1[N],pw1[N],base1=919,mod1=1e9+9; int get(int l,int r)// one base indexing 1<=l<=n { if(r<l) return 0; return ((pre[r]-(pre[l-1]*pw[r-l+1])%mod)%mod+mod)%mod; } int get1(int l,int r)// one base indexing 1<=l<=n { if(r<l) return 0; return ((pre1[r]-(pre1[l-1]*pw1[r-l+1])%mod1)%mod1+mod1)%mod1; } int main() { int n; cin>>n; string s; cin>>s; pre[0]=0; pw[0]=1; for(int i=1;i<=n;i++) pw[i]=(pw[i-1]*base)%mod; for(int i=1;i<=n;i++) pre[i]=((pre[i-1]*base)%mod+(s[i-1]-'A'))%mod; pre1[0]=0; pw1[0]=1; for(int i=1;i<=n;i++) pw1[i]=(pw1[i-1]*base1)%mod1; for(int i=1;i<=n;i++) pre1[i]=((pre1[i-1]*base1)%mod1+(s[i-1]-'A'))%mod1; set<int> posa; int len=(n-1)/2; for(int i=1;(n%2==1) and i<=n;i++) { ll fit=0; ll sec=0; ll fit1=0; ll sec1=0; int lf=(i-1); if(lf<=len) { fit=((get(1,i-1)*pw[len-lf])%mod+get(i+1,i+len-lf))%mod; sec=get(i+len-lf+1,n); fit1=((get1(1,i-1)*pw1[len-lf])%mod1+get1(i+1,i+len-lf))%mod1; sec1=get1(i+len-lf+1,i+len-lf+len); } else{ fit=get(1,len); sec=((get(len+1,i-1)*pw[n-i])%mod + get(i+1,n))%mod; fit1=get1(1,len); sec1=((get1(len+1,i-1)*pw1[n-i])%mod1 + get1(i+1,n))%mod1; } if(fit==sec and fit1==sec1) { posa.insert(i); } } if(posa.size()==0 or n%2!=1) { cout<<"NOT POSSIBLE\n"; } else if(posa.size()==1) { int j=*begin(posa); for(int i=1,p=0;p<len;i++) { if(i!=j) { cout<<s[i-1]; p++; } } cout<<endl; } else{ cout<<"NOT UNIQUE\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...