oj.uz

Submission #823944

# Submission time Handle Problem Language Result Execution time Memory
823944 2023-08-13T10:34:19 Z tch1cherin Necklace (Subtask 4) (BOI19_necklace4) C++17
15 / 15
 350 ms 440 KB 
#include <bits/stdc++.h>
using namespace std;
 
vector<int> prefix_function(string s) {
  int n = (int)s.size();
  vector<int> pi(n);
  for (int i = 1; i < n; ++i) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) {
      j = pi[j - 1];
    }
    if (s[i] == s[j]) {
      ++j;
    }
    pi[i] = j;
  }
  return pi;
}
 
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  string A, B;
  cin >> A >> B;
  tuple<int, int, int> ans = {0, 0, 0};
  for (int r = 0; r < 2; r++) {
    string S = A + "#" + B, T = B + "#" + A;
    for (int i = 0; i < (int)A.size(); i++) {
      vector<int> sPi = prefix_function(S.substr(i, S.size() - i));
      reverse(sPi.begin(), sPi.end());
      for (int j = 0; j < i; j++) {
        sPi.push_back(0);
      }
      reverse(sPi.begin(), sPi.end());
      string tt = T;
      tt = tt.substr(0, B.size() + i + 1);
      reverse(tt.begin(), tt.end());
      vector<int> tPi = prefix_function(tt);
      reverse(tPi.begin(), tPi.end());
      for (int j = 0; j < (int)B.size(); j++) {
        int rightleft = sPi[A.size() + j];
        int leftright = tPi[j];
        int res = rightleft + leftright, x = i - leftright, y = j - rightleft;
        if (r == 1) {
          y = (int)B.size() - res - y;
        }
        ans = max(ans, {res, x, y});
      }
    }
    reverse(B.begin(), B.end());
  }
  cout << get<0>(ans) << "\n" << get<1>(ans) << " " << get<2>(ans) << "\n";
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 416 KB Output is correct
2 Correct 298 ms 416 KB Output is correct
3 Correct 350 ms 440 KB Output is correct
4 Correct 272 ms 340 KB Output is correct
5 Correct 236 ms 424 KB Output is correct
6 Correct 260 ms 412 KB Output is correct
7 Correct 280 ms 412 KB Output is correct
8 Correct 297 ms 412 KB Output is correct
9 Correct 301 ms 420 KB Output is correct