oj.uz

Submission #664702

# Submission time Handle Problem Language Result Execution time Memory
664702 2022-11-27T08:18:12 Z Shin Necklace (Subtask 4) (BOI19_necklace4) C++14
15 / 15
 261 ms 528 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  auto build_kmp = [&](string s) {
    int n = (int) s.size();
    vector<int> f(n, 0);
    for (int i = 1, j = 0; i < n; i ++) {
      while (j > 0 && s[j] != s[i]) {
        j = f[j - 1]; 
      }
      if (s[j] == s[i]) {
        j ++;
      }
      f[i] = j;
    }
    return f;
  };
  auto calc = [&](string s, string t, bool rev) {
    int n = (int) s.size();
    int m = (int) t.size();
    tuple<int, int, int> res(0, 0, 0);
    for (int i = 0; i < n; i ++) {
      string rvs = s.substr(0, i);
      reverse(rvs.begin(), rvs.end());
      string rvt = t;
      reverse(rvt.begin(), rvt.end());
      vector<int> l_p = build_kmp(rvs + "#" + t);
      vector<int> r_p = build_kmp(s.substr(i, n - i) + "#" + rvt);
      for (int j = 0; j < m; j ++) {
        int tmp = l_p[i + j + 1] + r_p[n - i + m - j - 1];
        int l = i - l_p[i + j + 1];
        int r = j + 1 - l_p[i + j + 1];
        if (rev) {
          r = m - j - 1 - r_p[n - i + m - j - 1];
        }
        maximize(res, make_tuple(tmp, l, r));
      }
    }
    return res;
  };
  string s, t; cin >> s >> t;
  auto res = calc(s, t, 0);
  reverse(t.begin(), t.end());
  maximize(res, calc(s, t, 1));
  auto [len, l, r] = res;
  cout << len << "\n" << l << " " << r;
  return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:59:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |   auto [len, l, r] = res;
      |        ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 436 KB Output is correct
2 Correct 194 ms 420 KB Output is correct
3 Correct 261 ms 440 KB Output is correct
4 Correct 205 ms 428 KB Output is correct
5 Correct 182 ms 448 KB Output is correct
6 Correct 202 ms 444 KB Output is correct
7 Correct 208 ms 528 KB Output is correct
8 Correct 250 ms 444 KB Output is correct
9 Correct 222 ms 448 KB Output is correct