Submission #897122

#TimeUsernameProblemLanguageResultExecution timeMemory
897122pccNecklace (Subtask 4) (BOI19_necklace4)C++14
3 / 15
874 ms1092 KiB
#include <bits/stdc++.h> #include <bits/extc++.h> using namespace __gnu_pbds; using namespace std; #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> const int mxn = 3030; const ll mod = 712271227; inline ll pw(ll a,ll b){ ll re = 1; while(b){ if(b&1)re = re*a%mod; b>>=1; a = a*a%mod; } return re; } inline ll inv(ll k){ return pw(k,mod-2); } inline ll mad(ll a,ll b){ a+= b; return a>=mod?a-mod:a; } inline ll mub(ll a,ll b){ return mad(a,mod-b); } inline pll mad(pll a,pll b){ return make_pair(mad(a.fs,b.fs),mad(a.sc,b.sc)); } inline pll mub(pll a,pll b){ return make_pair(mub(a.fs,b.fs),mub(a.sc,b.sc)); } const pll p = {29,31}; gp_hash_table<ll,int> mp; string a,b; int N,M; const pll ip = {inv(p.fs),inv(p.sc)}; pii ans; pll ap[mxn],bp[mxn]; string tmp; inline bool found(string &s,int len){ pll val = make_pair(0,0); pll h = make_pair(1,1); for(int i = 0;i<len;i++){ val.fs = mad(val.fs,h.fs*(s[i]-'a'+1)%mod); val.sc = mad(val.sc,h.sc*(s[i]-'a'+1)%mod); h.fs = h.fs*p.fs%mod; h.sc = h.sc*p.sc%mod; } if(mp.find(val.fs*mod+val.sc) != mp.end()){ ans.fs = mp[val.fs*mod+val.sc]; return true; } for(int i = len;i<s.size();i++){ val = mub(val,make_pair(s[i-len]-'a'+1,s[i-len]-'a'+1)); val.fs = mad(val.fs,h.fs*(s[i]-'a'+1)%mod); val.sc = mad(val.sc,h.sc*(s[i]-'a'+1)%mod); val.fs = val.fs*ip.fs%mod; val.sc = val.sc*ip.sc%mod; if(mp.find(val.fs*mod+val.sc) != mp.end()){ ans.fs = mp[val.fs*mod+val.sc]; return true; } } return false; } inline bool check(int len){ if(!len){ ans.fs = ans.sc = 1; return true; } mp.clear(); pll sum = ap[len]; mp[sum.fs*mod+sum.sc] = 0; pll tp = make_pair(pw(p.fs,len),pw(p.sc,len)); for(int i = len;i<N;i++){ sum = mub(sum,make_pair(a[i-len]-'a'+1,a[i-len]-'a'+1)); sum = mad(sum,make_pair(tp.fs*(a[i]-'a'+1)%mod,tp.sc*(a[i]-'a'+1)%mod)); sum.fs = sum.fs*ip.fs%mod; sum.sc = sum.sc*ip.sc%mod; mp[sum.fs*mod+sum.sc] = i-len+1; } for(int i = 0;i+len<=M;i++){ tmp = b.substr(i,len); tmp += tmp; if(found(tmp,len)){ ans.sc = i; return true; } reverse(tmp.begin(),tmp.end()); if(found(tmp,len)){ ans.sc = i; return true; } } return false; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>a>>b; N = a.size(),M = b.size(); int l = 0,r = N; pll tmp = make_pair(1,1); for(int i = 0;i<N;i++){ ap[i+1] = ap[i]; ap[i+1].fs = mad(ap[i+1].fs,tmp.fs*(a[i]-'a'+1)%mod); ap[i+1].sc = mad(ap[i+1].sc,tmp.sc*(a[i]-'a'+1)%mod); tmp.fs = tmp.fs*p.fs%mod; tmp.sc = tmp.sc*p.sc%mod; } tmp = make_pair(1,1); for(int i = 0;i<M;i++){ bp[i+1] = bp[i]; bp[i+1].fs = mad(bp[i+1].fs,tmp.fs*(b[i]-'a'+1)%mod); bp[i+1].sc = mad(bp[i+1].sc,tmp.sc*(b[i]-'a'+1)%mod); tmp.fs = tmp.fs*p.fs%mod; tmp.sc = tmp.sc*p.sc%mod; } while(l != r){ int mid = (l+r+1)>>1; if(check(mid))l = mid; else r = mid-1; } check(l); cout<<l<<'\n'<<ans.fs<<' '<<ans.sc; }

Compilation message (stderr)

necklace.cpp: In function 'bool found(std::string&, int)':
necklace.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i = len;i<s.size();i++){
      |                  ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...