oj.uz

Submission #762637

# Submission time Handle Problem Language Result Execution time Memory
762637 2023-06-21T15:07:40 Z qrno Necklace (Subtask 4) (BOI19_necklace4) C++17
15 / 15
 314 ms 528 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(string const& s) {
  int n = size(s);
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i-1];
    while (j && s[i] != s[j]) j = pi[j-1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}

array<int, 3> solve(string const& s, string const& t, bool rev) {
  int n = size(s), m = size(t);

  string tr = t;
  reverse(begin(tr), end(tr));

  array<int, 3> ans{0, 0, 0};
  for (int i = 0; i < n; i++) {
    string s1 = s.substr(0, i), s2 = s.substr(i, n-i);
    reverse(begin(s1), end(s1));

    auto p1 = prefix_function(s1 + '$' + t);
    auto p2 = prefix_function(s2 + '$' + tr);

    for (int j = 1; j <= m; j++) {
      array<int, 3> a = {p1[i+j] + p2[n+m-i-j],
                         i - p1[i+j],
                         rev ? m - j - p2[n+m-i-j] : j - p1[i+j]};
      ans = max(ans, a);
    }
  }
  return ans;
}

int main() {
  string s, t;
  cin >> s >> t;

  auto ans = solve(s, t, false);
  reverse(begin(t), end(t));
  ans = max(ans, solve(s, t, true));
  cout << ans[0] << '\n' << ans[1] << ' ' << ans[2] << '\n';
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 420 KB Output is correct
2 Correct 226 ms 504 KB Output is correct
3 Correct 314 ms 412 KB Output is correct
4 Correct 225 ms 416 KB Output is correct
5 Correct 130 ms 412 KB Output is correct
6 Correct 138 ms 528 KB Output is correct
7 Correct 189 ms 412 KB Output is correct
8 Correct 220 ms 420 KB Output is correct
9 Correct 233 ms 420 KB Output is correct