Submission #503787

#TimeUsernameProblemLanguageResultExecution timeMemory
503787VictorNecklace (Subtask 4) (BOI19_necklace4)C++17
15 / 15
191 ms464 KiB
// #pragma GCC target ("avx,avx2,fma") // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast // #pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define per(i, a, b) for (int i = (b - 1); i >= (a); --i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) x.size() #define pb push_back #define debug(x) cout << #x << " = " << x << endl #define umap unordered_map #define uset unordered_set typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int INF = 1'000'000'007; vi kmp(string s,string p) { vi b(sz(p)+1); b[0]=-1; int i=0,j=-1; while(i<sz(p)) { while(0<=j&&p[i]!=p[j])j=b[j]; ++j; ++i; b[i]=j; } vi ans(sz(s)); i=0,j=0; while(i<sz(s)) { while(0<=j&&s[i]!=p[j])j=b[j]; ++j; ans[i]=j; ++i; if(j==sz(p))j=b[j]; } return ans; } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); string jill[2], jane[2]; cin >> jill[0] >> jane[0]; jill[1] = jill[0]; reverse(all(jill[1])); jane[1] = jane[0]; reverse(all(jane[1])); int n=sz(jill[0]),m=sz(jane[0]); int ans=0,sjill,sjane; rep(i,1,m) { vi lps=kmp(jill[0],jane[0].substr(i)),lsp=kmp(jill[1],jane[1].substr(m-i)); rep(j,0,n-1) { int a=lps[j],b=lsp[n-j-2]; if(a+b>ans) { ans=a+b; sjill=j-a+1; sjane=i-b; } } lps=kmp(jill[0],jane[1].substr(i)),lsp=kmp(jill[1],jane[0].substr(m-i)); rep(j,0,n-1) { int a=lps[j],b=lsp[n-j-2]; if(a+b>ans) { ans=a+b; sjill=j-a+1; sjane=m-i-a; } } } cout<<ans<<endl<<sjill<<' '<<sjane<<endl; return 0; }

Compilation message (stderr)

necklace.cpp: In function 'vi kmp(std::string, std::string)':
necklace.cpp:37:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while(i<sz(p)) {
      |            ^
necklace.cpp:45:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while(i<sz(s)) {
      |            ^
necklace.cpp:50:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         if(j==sz(p))j=b[j];
      |             ^
necklace.cpp: In function 'int main()':
necklace.cpp:96:34: warning: 'sjane' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     cout<<ans<<endl<<sjill<<' '<<sjane<<endl;
      |                                  ^~~~~
necklace.cpp:96:29: warning: 'sjill' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     cout<<ans<<endl<<sjill<<' '<<sjane<<endl;
      |                             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...