Submission #123002

#	Time	Username	Problem	Language	Result	Execution time	Memory
123002		model_code	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	393 ms	504 KiB

necklace

//DP: time O(n^2), mem O(n) 
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int solve_noflip(string &s, string &t, int *loc) {
  int n = s.size();  // vertical
  int m = t.size();  // horizontal
  int res = 0;
  vector< short > forw_back_len(m + 1);
  vector< short > cur_v_len(n + m + 1);  // offset -n
  vector< short > cur_v_y(n + m + 1);
  for (int i = 0; i <= n; ++i) cur_v_y[n - i] = i;
  vector< short > cur_h_len(m + 1);
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= m; ++j) forw_back_len[j] = max(0, forw_back_len[j] - 1);
    for (int j = 0; j <= m; ++j) {
      int idx = n - i + j;
      while (cur_v_y[idx] - cur_v_len[idx] == i) {
        int y = cur_v_y[idx];
        // x-j == y-i
        int x = y - i + j;
        forw_back_len[x] = max(forw_back_len[x], cur_v_len[idx]);
        if (y == n || x == m) {
          cur_v_y[idx] = -1;
        } else {
          ++cur_v_y[idx];
          if (s[y] == t[x]) {
            ++cur_v_len[idx];
          } else {
            cur_v_len[idx] = 0;
          }
        }
      }
    }
    vector< short > back_forw_len(m + 1);
    for (int j = 0; j <= m; ++j) {
      int nj = j - cur_h_len[j];
      back_forw_len[nj] = max(back_forw_len[nj], cur_h_len[j]);
    }
    for (int j = 1; j <= m; ++j) {
      back_forw_len[j] = max((int)back_forw_len[j], back_forw_len[j - 1] - 1);
    }
    for (int j = 0; j <= m; ++j) {
      if (forw_back_len[j] + back_forw_len[j] > res) {
        res = forw_back_len[j] + back_forw_len[j];
        loc[0] = i - back_forw_len[j];
        loc[1] = j - forw_back_len[j];
      }
    }
    if (i < n) {
      for (int j = m - 1; j >= 0; --j) {
        if (s[i] == t[j]) {
          cur_h_len[j + 1] = cur_h_len[j] + 1;
        } else {
          cur_h_len[j + 1] = 0;
        }
      }
      cur_h_len[0] = 0;
    }
  }
  return res;
}

int solve(string &s, string &t, int *loc) {
  int loc_noflip[2];
  int res = solve_noflip(s, t, loc_noflip);
  reverse(t.begin(), t.end());
  int loc_flip[2];
  int res_flip = solve_noflip(s, t, loc_flip);
  if (res_flip > res) {
    res = res_flip;
    loc[0] = loc_flip[0];
    loc[1] = (int)t.size() - loc_flip[1] - res;
  } else {
    for (int i = 0; i < 2; ++i) loc[i] = loc_noflip[i];
  }
  return res;
}

int main() {
  cin.sync_with_stdio(false);
  string s, t;
  cin >> s >> t;
  int loc[2];
  int res = solve(s, t, loc);
  cout << res << '\n';
  if (res) {
    cout << loc[0] << ' ' << loc[1] << '\n';
  }
  return 0;
}

• Subtask 1: 15 / 15