Submission #1094015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094015		Tam_theguide	Matching (CEOI11_mat)	C++14	100 / 100	172 ms	51976 KiB

mat

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

const int MAXN = 1e6;

int n, m, idx[MAXN + 5], s[2 * MAXN + 5], lt[MAXN + 5], rt[MAXN + 5], pi[2 * MAXN + 5];

struct linked_list {
    int n, *l, *r;

    linked_list(int n_) :
        n(n_), l(new int[n_ + 5]), r(new int[n_ + 5]) {
            for (int i = 1; i <= n; i++) {
                l[i] = i - 1;
                r[i] = i + 1;
            }
        }

    void del(int i) {
        int l_ = l[i], r_ = r[i];
        r[l_] = r_;
        l[r_] = l_;
    }
};

bool check(int i, int j) {
    if (i == n + 1) return false;
    if (lt[i] && s[j - i + lt[i]] > s[j]) 
        return false;
    if (rt[i] && s[j + rt[i] - i] < s[j])
        return false;
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> idx[i];
        s[idx[i]] = i;
    }
    
    s[n + 1] = 0;

    for (int i = n + 2; i <= n + 1 + m; i++)
        cin >> s[i];

    linked_list lk(n);

    for (int i = n; i >= 1; i--) {
        lt[i] = idx[lk.l[s[i]]];
        rt[i] = idx[lk.r[s[i]]];
        lk.del(s[i]);
    }

    vector<int> ans(0);
    for (int i = 2; i <= n + m + 1; i++) {
        if (i == n + 1) continue;
        int tmp = pi[i - 1];
        while (tmp > 0 && !check(tmp + 1, i))
            tmp = pi[tmp];
        if (check(tmp + 1, i)) pi[i] = tmp + 1;
        if (i > n + 1 && pi[i] == n) ans.push_back(i - 2 * n);
    }   

    // for (int i = 1; i <= n; i++)    
    //     cout << s[i] << " ";
    // cout << '\n';

    // for (int i = 1; i <= n; i++) {
    //     cout << "phan tu " << i << " : " << lt[i] << ", " << rt[i] << '\n';
    // }

    // for (int i = n + 2; i <= n + m + 1; i++)
    //     cout << pi[i] << " ";
    // cout << '\n';

    cout << (int)ans.size() << '\n';
    for (auto c : ans) cout << c << " ";
}

• 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