oj.uz

Submission #624346

# Submission time Handle Problem Language Result Execution time Memory
624346 2022-08-08T02:26:37 Z KoD Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 575 ms 476 KB 
#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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 12 ms 304 KB Output is correct
7 Correct 11 ms 300 KB Output is correct
8 Correct 11 ms 296 KB Output is correct
9 Correct 11 ms 304 KB Output is correct
10 Correct 11 ms 212 KB Output is correct
11 Correct 11 ms 304 KB Output is correct
12 Correct 12 ms 212 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 12 ms 304 KB Output is correct
7 Correct 11 ms 300 KB Output is correct
8 Correct 11 ms 296 KB Output is correct
9 Correct 11 ms 304 KB Output is correct
10 Correct 11 ms 212 KB Output is correct
11 Correct 11 ms 304 KB Output is correct
12 Correct 12 ms 212 KB Output is correct
13 Correct 575 ms 464 KB Output is correct
14 Correct 537 ms 472 KB Output is correct
15 Correct 564 ms 340 KB Output is correct
16 Correct 539 ms 352 KB Output is correct
17 Correct 508 ms 472 KB Output is correct
18 Correct 530 ms 476 KB Output is correct
19 Correct 535 ms 468 KB Output is correct
20 Correct 555 ms 352 KB Output is correct
21 Correct 553 ms 468 KB Output is correct