Submission #896719

#	Time	Username	Problem	Language	Result	Execution time	Memory
896719		box	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	263 ms	596 KiB

necklace

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: ", bug_h(__VA_ARGS__)
#else
#define cerr if (false) cerr
#define bug(...)
#endif

#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> pi;

ar<int, 3> solve(const string& S, const string& T) {
    int N = sz(S), M = sz(T);
    // vector dpL(N, vi(M)), dpR(N, vi(M));
    vi rollL(M), rollR(M);
    vi c(N + M), cc(N + M), ii(N + M);
    for (int d = -(N - 1); d < M; d++) {
        // vector<pi> ij;
        for (int i = 0; i < N; i++) {
            int j = i + d;
            if (0 <= j && j < M) {
                ii[N + d] = i;
                // ij.push_back({i, j});
            }
        }
        /*
        reverse(all(ij));
        int c = 0;
        for (auto [i, j] : ij) {
            if (S.at(i) == T.at(j)) c++;
            else c = 0;
            if (c) {
                int x = i + c - 1, y = j + c - 1;
                cerr << x << ' ';
                // bug(i, j, x, y, c);
                dpL.at(x).at(j) = max(dpL.at(x).at(j), c);
                dpR.at(i).at(y) = max(dpR.at(i).at(y), c);
            }
        }
        cerr << endl;
        */
    }
    /*
    for (int j = 0; j < M; j++) for (int i = N - 1; i > 0; i--)
        dpL.at(i - 1).at(j) = max(dpL.at(i - 1).at(j), dpL.at(i).at(j) - 1);
    for (int i = 0; i < N; i++) for (int j = M - 1; j > 0; j--)
        dpR.at(i).at(j - 1) = max(dpR.at(i).at(j - 1), dpR.at(i).at(j) - 1);
    */
    ar<int, 3> best{0, 0, 0};
    for (int i = N; i >= 0; i--) {
        if (i) {
            for (int j = 0; j < M; j++) {
                rollL.at(j)--;
                rollL[j] = max(rollL[j], 0);
            }
            for (int d = -(N - 1); d < M; d++) {
                int i_ = ii[N + d], j = ii[N + d] + d, c_ = (S[i_] == T[j] ? cc[N + d] + 1 : 0);
                while (0 <= j && j < M && i_ + c_ - 1 == i - 1) {
                    rollL.at(j) = max(rollL.at(j), c_);
                    ii[N + d]--;
                    cc[N + d] = c_;
                    i_ = ii[N + d], j = ii[N + d] + d, c_ = (S[i_] == T[j] ? cc[N + d] + 1 : 0);
                }
            }
        }
        fill(all(rollR), 0);
        if (i < N) {
            for (int d = -(N - 1); d < M; d++) {
                int j = i + d;
                if (0 <= j && j < M) {
                    if (S[i] == T[j]) c[N + d]++;
                    else c[N + d] = 0;
                    if (c[N + d]) {
                        int y = j + c[N + d] - 1;
                        rollR[y] = max(rollR[y], c[N + d]);
                    }
                }
            }
        }
        for (int j = M - 1; j > 0; j--)
            rollR[j - 1] = max(rollR[j - 1], rollR[j] - 1);
        for (int j = M; j >= 0; j--) {
            int L = i > 0 && j < M ? rollL.at(j) : 0;
            int R = j > 0 && i < N ? rollR.at(j - 1) : 0;
            /*
            if (i > 0 && j < M && rollL.at(j) != dpL.at(i - 1).at(j)) bug(i - 1, j, rollL.at(j), dpL.at(i - 1).at(j));
            if (j > 0 && i < N && rollR.at(j - 1) != dpR.at(i).at(j - 1)) bug(i, j - 1, rollR.at(j - 1), dpR.at(i).at(j - 1));
            */
            best = max(best, {L + R, i - L, j - R});
        }
    }
    bug(best[0], best[1], best[2]);
    return best;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    string S, T;
    cin >> S >> T;
    auto one = solve(S, T);
    reverse(begin(T), end(T));
    auto two = solve(S, T);
    reverse(begin(T), end(T));
    two[2] = sz(T) - two[2] - two[0];
    auto best = max(one, two);
    cout << best[0] << '\n';
    cout << best[1] << ' ' << best[2] << '\n';
}

• Subtask 1: 15 / 15