Submission #1190343

#TimeUsernameProblemLanguageResultExecution timeMemory
1190343AlgorithmWarrior세 명의 친구들 (BOI14_friends)C++20
100 / 100
135 ms18796 KiB
#include <bits/stdc++.h> using namespace std; int const MOD=1e9+7; int const BASE=31; int const MAX=2000005; int n; char sir[MAX]; int hashes[MAX]; int bpow[MAX]; int ans_hash,ans_id; void read(){ cin>>n; int i; for(i=1;i<=n;++i) cin>>sir[i]; } void precalc(){ int i; bpow[0]=1; for(i=1;i<MAX;++i) bpow[i]=1LL*BASE*bpow[i-1]%MOD; for(i=1;i<=n;++i) hashes[i]=(1LL*BASE*hashes[i-1]%MOD+sir[i]-'A'+1)%MOD; } int hash_intv(int l,int r){ return (hashes[r]-1LL*hashes[l-1]*bpow[r-l+1]%MOD+MOD)%MOD; } int hash_2intv(int l1,int r1,int l2,int r2){ return (1LL*hash_intv(l1,r1)*bpow[r2-l2+1]%MOD+hash_intv(l2,r2))%MOD; } void solve(){ if(n%2==0) return; int i; for(i=1;i<=n;++i){ int hsh1,hsh2; if(i<=n/2+1){ hsh1=hash_2intv(1,i-1,i+1,n/2+1); hsh2=hash_intv(n/2+2,n); } else{ hsh1=hash_intv(1,n/2); hsh2=hash_2intv(n/2+1,i-1,i+1,n); } if(hsh1==hsh2){ if(!ans_hash){ ans_hash=hsh1; ans_id=i; } else if(ans_hash!=hsh1) ans_id=0; } } } void answer(){ if(ans_id){ int i; for(i=1;i<=n/2+(ans_id<=n/2);++i) if(i!=ans_id) cout<<sir[i]; } else{ if(ans_hash) cout<<"NOT UNIQUE"; else cout<<"NOT POSSIBLE"; } } int main() { read(); precalc(); solve(); answer(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...