oj.uz

Submission #823924

# Submission time Handle Problem Language Result Execution time Memory
823924 2023-08-13T10:13:02 Z tch1cherin Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 782 ms 282908 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;
    vector piS(S.size(), vector<int>(S.size())), piT(T.size(), vector<int>(T.size()));
    for (int i = 0; i < (int)S.size(); i++) {
      vector<int> sPi = prefix_function(S.substr(i, S.size() - i));
      vector<int> tPi = prefix_function(T.substr(i, S.size() - i));
      reverse(sPi.begin(), sPi.end());
      reverse(tPi.begin(), tPi.end());
      for (int j = 0; j < i; j++) {
        sPi.push_back(0);
        tPi.push_back(0);
      }
      reverse(sPi.begin(), sPi.end());
      reverse(tPi.begin(), tPi.end());
      piS[i] = sPi, piT[i] = tPi;
    }
    for (int i = 0; i < (int)A.size(); i++) {
      for (int j = 0; j < (int)B.size(); j++) {
        int rightleft = piS[i][A.size() + j];
        int leftright = piT[j][B.size() + i];
        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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 660 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 660 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 12 ms 5440 KB Output is correct
7 Correct 11 ms 5476 KB Output is correct
8 Correct 11 ms 4564 KB Output is correct
9 Correct 11 ms 5204 KB Output is correct
10 Correct 14 ms 5460 KB Output is correct
11 Correct 12 ms 5372 KB Output is correct
12 Correct 11 ms 5060 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 660 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 12 ms 5440 KB Output is correct
7 Correct 11 ms 5476 KB Output is correct
8 Correct 11 ms 4564 KB Output is correct
9 Correct 11 ms 5204 KB Output is correct
10 Correct 14 ms 5460 KB Output is correct
11 Correct 12 ms 5372 KB Output is correct
12 Correct 11 ms 5060 KB Output is correct
13 Correct 782 ms 282908 KB Output is correct
14 Correct 734 ms 282856 KB Output is correct
15 Correct 759 ms 266240 KB Output is correct
16 Correct 733 ms 278356 KB Output is correct
17 Correct 663 ms 272804 KB Output is correct
18 Correct 693 ms 280892 KB Output is correct
19 Correct 692 ms 280280 KB Output is correct
20 Correct 722 ms 272472 KB Output is correct
21 Correct 737 ms 275540 KB Output is correct