Submission #976293

#TimeUsernameProblemLanguageResultExecution timeMemory
976293roctes7Necklace (Subtask 4) (BOI19_necklace4)C++17
0 / 15
1536 ms35484 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define fastio \ ios_base::sync_with_stdio(false); \ cin.tie(NULL); const double eps = 1e-6; const int MAX = 3e3+3; int pi[3003][3003]; int n; string s; void kmp(int sta){ for (int i = 1; i < n; i++) { int j = pi[sta][i-1]; while (j > 0 && s[i] != s[j]) j = pi[sta][j-1]; if (s[i] == s[j]) j++; pi[sta][i] = j; } } string t1,t2; pair<int,pair<int,int>> solve(){ for(int i=0;i<t1.size();i++){ s = ""; for(int j=i;j<t1.size();j++)s+=t1[j]; for(int j=0;j<i;j++)s+=t1[j]; s+="#"; s+=t2; n = s.size(); kmp(i); //cout<<s<<endl; } int l = 1; int r = t1.size(); int ans = -1; int ansl = -1; int ansr = -1; while(l<=r){ int k = (l+r)/2; bool check = false; for(int i=0;i<t1.size();i++){ if(check)break; for(int j=t1.size()+1;j<n;j++){ int cur = pi[i][j]; if(cur>=k){ check = true; if(k>ans){ ans = cur; ansl = i; ansr = j-(t1.size()+1)-cur+1; } break; } int stil = k - cur; if(cur==0||i+cur>=t1.size()||j-cur<t1.size()+1)continue; int cur2 = pi[i+cur][j-cur]; if(cur2>=stil){ check = true; if(k>ans){ ans = k; ansl = i; ansr = j-(t1.size()+1)-k+1; } break; } } } if(check){ l = k+1; }else r = k-1; } return {ans,{ansl,ansr}}; } int main(){ fastio; cin>>t1>>t2; auto ans1 = solve(); reverse(t2.begin(),t2.end()); auto ans2 = solve(); ans2.se.se = ans2.se.se + ans2.fi-1; ans2.se.se = t2.size()-ans2.se.se-1; if(ans2.se.se<0)ans2.se.se = t2.size()-1+ans2.se.se; pair<int,pair<int,int>> ans = max(ans1,ans2); cout<<ans.fi<<endl<<ans.se.fi<<" "<<ans.se.se; return 0; }

Compilation message (stderr)

necklace.cpp: In function 'std::pair<int, std::pair<int, int> > solve()':
necklace.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |        for(int i=0;i<t1.size();i++){
      |                    ~^~~~~~~~~~
necklace.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int j=i;j<t1.size();j++)s+=t1[j];
      |                     ~^~~~~~~~~~
necklace.cpp:52:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i=0;i<t1.size();i++){
      |                     ~^~~~~~~~~~
necklace.cpp:66:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |                 if(cur==0||i+cur>=t1.size()||j-cur<t1.size()+1)continue;
      |                            ~~~~~^~~~~~~~~~~
necklace.cpp:66:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |                 if(cur==0||i+cur>=t1.size()||j-cur<t1.size()+1)continue;
      |                                              ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...