Submission #1126100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126100		Zero_OP	Matching (CEOI11_mat)	C++20	54 / 100	900 ms	82464 KiB

mat

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, M;
    cin >> N >> M;

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

    for(int i = N; i < N + M; ++i){
        cin >> A[i];
    }

    vector<int> L(N + M, -1), R(N + M, -1);

    set<pair<int, int>> v;
    for(int i = 0; i < N; ++i){
        auto it = v.upper_bound({A[i], -1});
        if(it != v.begin()){
            L[i] = prev(it) -> second;
        }

        if(it != v.end()){
            R[i] = it -> second;
        }

        v.insert({A[i], i});
    }

    function<bool(int, int)> isomorphic = [&](int j, int i){
        if(j == N) return false;
        if(L[j] != -1 && A[i - j + L[j]] > A[i]) return false;
        if(R[j] != -1 && A[i - j + R[j]] < A[i]) return false;
        return true;
    };

    vector<int> ans;
    vector<int> pi(N + M);
    for(int i = 1, j = 0; i < N + M; ++i){
        while(j > 0 && !isomorphic(j, i)) j = pi[j - 1];
        if(isomorphic(j, i)) ++j;

        if(j == N){
            ans.push_back(i - 2 * N + 2);
        }

        pi[i] = j;
    }

    cout << (int)ans.size() << '\n';
    for(int i : ans) cout << i << ' '; cout << '\n';

    return 0;
}

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