Submission #310580

#	Time	Username	Problem	Language	Result	Execution time	Memory
310580		adrianbudau	Matching (CEOI11_mat)	C++17	100 / 100	307 ms	42488 KiB

mat

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

vector<int> invert(const vector<int> &P) {
    vector<int> where(P.size());
    for (size_t i = 0; i < P.size(); ++i)
        where[P[i]] = i;
    return where;
}

bool check(int position, const vector<int> &prev, const vector<int> &next, const vector<int> &text, int needle) {
    int p = prev[position];
    int n = next[position];
    if (p != -1) {
        p += needle - position;
        if (text[p] > text[needle])
            return false;
    }
    if (n != -1) {
        n += needle - position;
        if (text[n] < text[needle])
            return false;
    }
    return true;
}

tuple<vector<int>, vector<int>, vector<int>> prefix(const vector<int>& P) {
    int N = P.size();
    vector<int> where(N);
    for (int i = 0; i < N; ++i)
        where[P[i]] = i;


    vector<int> prev(N, -1), next(N, -1), pi(N, 0);
    for (int i = 0; i < N; ++i) {
        if (P[i] > 0)
            prev[i] = where[P[i] - 1];
        if (P[i] + 1 < N)
            next[i] = where[P[i] + 1];
    }

    for (int i = N - 1; i >= 0; --i) {
        auto p = prev[i];
        auto n = next[i];
        if (p != -1) {
            next[p] = n;
        }
        if (n != -1) {
            prev[n] = p;
        }
    }

    int k = 0;
    for (int i = 1; i < N; ++i) {
        while (k != 0 && !check(k, prev, next, P, i))
            k = pi[k - 1];
        if (check(k, prev, next, P, i))
            ++k;
        pi[i] = k;
    }
    return {prev, next, pi};
}

int main() {
    ios::sync_with_stdio(false);

    int N, M; cin >> N >> M;
    vector<int> P(N);
    for (int i = 0; i < N; ++i) {
        cin >> P[i];
        --P[i];
    }

    auto [prev, next, pi] = prefix(invert(P));
    vector<int> T(M);
    for (int i = 0; i < M; ++i) {
        cin >> T[i];
    }

    vector<int> answer;
    int k = 0;
    for (int i = 0; i < M; ++i) {
        while (k != 0 && !check(k, prev, next, T, i))
            k = pi[k - 1];
        if (check(k, prev, next, T, i))
            ++k;
        if (k == int(P.size())) {
            answer.push_back(i - P.size() + 1);
            k = pi[k - 1];
        }
    }

    cout << answer.size() << "\n";
    for (auto &x : answer)
        cout << x + 1 << " ";
    cout << "\n";
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10