제출 #209614

#제출 시각아이디문제언어결과실행 시간메모리
209614thebesNecklace (Subtask 1-3) (BOI19_necklace1)C++14
45 / 85
1591 ms380 KiB
#include <bits/stdc++.h> #define DEBUG 1 using namespace std; namespace output{ void __(short x){cout<<x;} void __(unsigned x){cout<<x;} void __(int x){cout<<x;} void __(long long x){cout<<x;} void __(unsigned long long x){cout<<x;} void __(double x){cout<<x;} void __(long double x){cout<<x;} void __(char x){cout<<x;} void __(const char*x){cout<<x;} void __(const string&x){cout<<x;} void __(bool x){cout<<(x?"true":"false");} template<class S,class T> void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");} template<class T> void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class T> void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class T> void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class S,class T> void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} void pr(){cout<<"\n";} template<class S,class... T> void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);} } using namespace output; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<int,char> pic; typedef pair<double,double> pdd; typedef pair<ld,ld> pld; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<int,vi> piv; #define pb push_back #define fox(i,x,y) for(int i=(x);i<=(y);i++) #define foxr(i,x,y) for(int i=(y);i>=(x);i--) const int MN = 3003; string s, t; int n, m, i, hsh[2][MN], pw[MN]={1}, pre[MN], suf[MN], st[MN], len[MN], lo, hi, lim1, lim2, ans, sw, fl, ree, k, sh; int gethsh(int id,int x,int y){return hsh[id][y]-hsh[id][x-1]*pw[y-x+1];} pii sna; queue<pii> hm; void solve(){ for(int i=1;i<=m;i++) hsh[1][i]=hsh[1][i-1]*133+t[i-1]-'a'+1; memset(pre,0,sizeof(pre)); memset(suf,0,sizeof(suf)); memset(st,0,sizeof(st)); memset(len,0,sizeof(len)); k = min(m,lim2); for(int i=1;i<=n;i++){ lo=0, hi=min(i,k); while(lo<hi){ int mid = (lo+hi)/2; if(gethsh(0,i-mid,i)==gethsh(1,m-mid,m)) lo=mid+1; else hi=mid; } suf[i]=lo; } while(hm.size()) hm.pop(); for(int i=n;i>=1;i--){ if(suf[i]) hm.push({suf[i],i}); while(hm.size()){ if(hm.front().second-hm.front().first+1>i) hm.pop(); else break; } if(hm.size()){ st[i] = lim2-hm.front().first; len[i] = hm.front().second-i+1; } else st[i] = lim2; } k = min(m,lim1); for(int i=1;i<=n;i++){ lo=0, hi=min(n-i+1,k); while(lo<hi){ int mid = (lo+hi)/2; if(gethsh(0,i,i+mid)==gethsh(1,1,1+mid)) lo=mid+1; else hi=mid; } pre[i]=lo; } while(hm.size()) hm.pop(); for(int i=1;i<=n;i++){ if(pre[i]) hm.push({pre[i],i}); while(hm.size()){ if(hm.front().second+hm.front().first-1<i) hm.pop(); else break; } if(hm.size()){ len[i] = i-hm.front().second+1; if(len[i]+len[i+1]>ans){ ans = len[i]+len[i+1]; if(sw) sna = {n-(i+len[i+1]), st[i+1]}; else sna = {hm.front().second-1, st[i+1]}; } } } } int main(){ cin >> s >> t; n = s.size(), m = t.size(); for(i=1;i<MN;i++) pw[i]=133*pw[i-1]; for(i=1;i<=n;i++) hsh[0][i]=hsh[0][i-1]*133+s[i-1]-'a'+1; lim1 = 0; lim2 = m; solve(); for(i=1;i<=m;i++){ lim1++; lim2--; char ch = t.back(); t.erase(t.end()-1); t.insert(t.begin(),ch); solve(); } for(i=0;i<s.size()/2;i++) swap(s[i],s[s.size()-i-1]); for(i=1;i<=n;i++) hsh[0][i]=hsh[0][i-1]*133+s[i-1]-'a'+1; lim1 = 0; lim2 = m; sw = 1; solve(); for(i=1;i<=m;i++){ lim1++; lim2--; char ch = t.back(); t.erase(t.end()-1); t.insert(t.begin(),ch); solve(); } printf("%d\n%d %d\n",ans,sna.first,sna.second); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

necklace.cpp: In function 'int main()':
necklace.cpp:128:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<s.size()/2;i++)
             ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...