Submission #624345

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
624345	2022-08-08T02:25:25 Z	KoD	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	606 ms	488 KB

necklace

#include <bits/stdc++.h>

using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;

vector<int> z_algo(const string& S) {
    const int N = (int)S.size();
    vector<int> ret(N);
    ret[0] = N;
    int i = 1, j = 0;
    while (i < N) {
        while (i + j < N and S[j] == S[i + j]) {
            j += 1;
        }
        if (j == 0) {
            i += 1;
            continue;
        }
        ret[i] = j;
        int k = 1;
        while (i + k < N and k + ret[k] < j) {
            ret[i + k] = ret[k];
            k += 1;
        }
        i += k;
        j -= k;
    }
    return ret;
}

tuple<int, int, int> solve(const string& S, const string& T) {
    const int N = (int)S.size();
    const int M = (int)T.size();
    int best = 0, s_k = 0, t_k = 0;
    for (int split = 0; split <= N; ++split) {
        const auto A = [&] {
            std::string s;
            for (int i = split; i < N; ++i) {
                s += S[i];
            }
            s += '$';
            for (int i = 0; i < M; ++i) {
                s += T[i];
            }
            const auto z = z_algo(s);
            vector<int> ret(M + 1);
            for (int i = 0; i < M; ++i) {
                ret[i] = z[N - split + 1 + i];
            }
            return ret;
        }();
        const auto B = [&] {
            std::string s;
            for (int i = split - 1; i >= 0; --i) {
                s += S[i];
            }
            s += '$';
            for (int i = M - 1; i >= 0; --i) {
                s += T[i];
            }
            const auto z = z_algo(s);
            vector<int> ret(M + 1);
            for (int i = 0; i < M; ++i) {
                ret[M - i] = z[split + 1 + i];
            }
            return ret;
        }();
        vector<int> min_i(M + 1, M);
        for (int i = M; i >= 0; --i) {
            min_i[std::min(A[i] + i, M)] = i;
        }
        for (int i = M; i > 0; --i) {
            min_i[i - 1] = std::min(min_i[i - 1], min_i[i]);
        }
        for (int j = 0; j <= M; ++j) {
            const int i = min_i[j - B[j]];
            if (best < j - i) {
                best = j - i;
                s_k = split - B[j];
                t_k = i;
            }
        }
    }
    return {best, s_k, t_k};
}

int main() {
    string S, T;
    std::cin >> S >> T;
    const auto [k0, i0, j0] = solve(S, T);
    std::reverse(T.begin(), T.end());
    const auto [k1, i1, j1] = solve(S, T);
    if (k0 > k1) {
        std::cout << k0 << '\n' << i0 << ' ' << j0 << '\n';
    } else {
        std::cout << k1 << '\n' << i1 << ' ' << (int)T.size() - (j1 + k1) << '\n';
    }
    return 0;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	587 ms	356 KB	Output is correct
2	Correct	541 ms	356 KB	Output is correct
3	Correct	606 ms	468 KB	Output is correct
4	Correct	485 ms	356 KB	Output is correct
5	Correct	493 ms	352 KB	Output is correct
6	Correct	548 ms	488 KB	Output is correct
7	Correct	558 ms	356 KB	Output is correct
8	Correct	551 ms	356 KB	Output is correct
9	Correct	557 ms	356 KB	Output is correct