Submission #957525

#TimeUsernameProblemLanguageResultExecution timeMemory
957525YassirSalamaThree Friends (BOI14_friends)C++17
0 / 100
14 ms12800 KiB
#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() #define int long long const int MAXN=2e5+100; const int MOD1=1e9+7,P=31; int binpow(int a,int b,int mod){ int res=1; while(b){ if(b&1) res=(res%mod*a%mod)%mod; a=(a%mod*a%mod)%mod; b>>=1; } return res%mod; } int invmod(int a,int mod){ return binpow(a,mod-2,mod); } int pref1[MAXN]; int inv1[MAXN]; const int MOD2=1404543827; const int P2=83; int pref2[MAXN]; int inv2[MAXN]; int sum1(int l,int r){ if(l==0) return pref1[r]%MOD1; else return ((pref1[r]-(ll)pref1[l-1]+3LL*MOD1)%MOD1*(invmod(binpow(P,l,MOD1),MOD1)%MOD1))%MOD1; } int sum2(int l,int r){ if(l==0) return pref2[r]%MOD2; else return ((pref2[r]-(ll)pref2[l-1]+3LL*MOD2)%MOD2*(invmod(binpow(P2,l,MOD2),MOD2)%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]=(inv1[i-1]%MOD1*(inv1[1]%MOD1))%MOD1; } int 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]+=(x%MOD1*c%MOD1)%MOD1; c=(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]+=(x%MOD2*c%MOD2)%MOD2; c=(c%MOD2*P2%MOD2)%MOD2; } vector<pair<int,int>> ans; 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(sum1(l1,r1)==sum1(l2,r2)&&sum2(l1,r1)==sum2(l2,r2)) ans.pb({l1,r1}); else continue; } if(i<=r1){ int t=i-1; int t1=i+1; int s1=0; s1+=sum1(l1,t); s1%=MOD1; s1+=binpow(P,(i%((n-2)/2+1)),MOD1)*sum1(t1,r1); s1%=MOD1; s1+=MOD1; s1%=MOD1; int s2=0; s2+=sum2(l1,t); s2%=MOD2; s2+=binpow(P2,(i%((n-2)/2+1)),MOD2)*sum2(t1,r1); s2%=MOD2; s2+=MOD2; s2%=MOD2; if(s1==sum1(l2,r2)%MOD1&&s2==sum2(l2,r2)%MOD2) ans.pb({l2,r2}); }else{ int t=i-1; int t1=i+1; int s1=0; s1+=sum1(l2,t); s1%=MOD1; s1+=binpow(P,(i%((n-2)/2+1)),MOD1)*sum1(t1,r2); s1%=MOD1; s1+=MOD1; s1%=MOD1; int s2=0; s2+=sum2(l2,t); s2%=MOD2; s2+=binpow(P2,(i%((n-2)/2+1)),MOD2)*sum2(t1,r2); s2%=MOD2; s2+=MOD2; s2%=MOD2; // dbg(s2,sum2(l1,r1)) if(s1==sum1(l1,r1)&&s2==sum2(l1,r1)%MOD2) ans.pb({l1,r1}); } } if(ans.size()==1){ pair<int,int> anss=ans[0]; cout<<s.substr(anss.F,anss.S-anss.F+1)<<endl; }else{ if(ans.empty()){ cout<<"NOT POSSIBLE"<<endl; return 0; } cout<<"NOT UNIQUE"<<endl; return 0; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...