Submission #1204487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204487		tarche	Necklace (Subtask 4) (BOI19_necklace4)	C++20	15 / 15	248 ms	576 KiB

necklace

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = (int)(b) - 1; i >= (a); --i)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
using vb = vector<bool>;
using vl = vector<ll>;

vi pi(const string &s) {
  vi p(sz(s));
  rep(i, 1, sz(s)) {
    int g = p[i - 1];
    while (g && s[i] != s[g]) g = p[g - 1];
    p[i] = g + (s[i] == s[g]);
  }
  return p;
}

tuple<int, int, int> solve(const string &s, const string &t) {
  const int n = sz(s), m = sz(t);

  tuple<int, int, int> ans = {0, 0, 0};
  rep(i, 0, n) {
    string s1 = s.substr(0, i), s2 = s.substr(i, n - i);
    string t1 = t, t2 = t;
    reverse(all(s1)), reverse(all(t2));
    const auto p = pi(s1 + '$' + t1), q = pi(s2 + '$' + t2);

    rep(j, 1, m + 1) {
      int lhs = p[i + j], rhs = q[(n - i) + (m - j)];
      ans = max(ans, tuple(lhs + rhs, i - lhs, j - lhs));
    }
  }

  return ans;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  string s, t;
  cin >> s >> t;

  auto normal = solve(s, t);
  reverse(all(t));
  auto reversed = solve(s, t);
  get<2>(reversed) = get<0>(reversed) + get<2>(reversed) - 1;
  get<2>(reversed) = sz(t) - get<2>(reversed) - 1;

  auto [x, y, z] = max(normal, reversed);
  cout << x << '\n' << y << ' ' << z << '\n';
}

• Subtask 1: 15 / 15