Submission #151859

#	Time	Username	Problem	Language	Result	Execution time	Memory
151859		forestryks	Matching (CEOI11_mat)	C++14	36 / 100	2050 ms	44980 KiB

mat

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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define rep(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define all(x) (x).begin(), (x).end()
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define f first
#define s second

const int MAXN = 1e6 + 5;
int m, n;
int p[MAXN];
int a[MAXN];

void ps(set<pair<int, int>> &s) {
    for (auto it : s) {
        cout << it.f << ' ' << it.s << endl;
    }
    cout << endl;
}

int main() {
    FAST_IO;
    cin >> m >> n;
    rep(i, m) {
        cin >> p[i];
    }
    rep(i, n) {
        cin >> a[i];
    }

    set<pair<int, int>> s, s1;
    rep(i, m) {
        s.insert({a[i], i});
        s1.insert({i, p[i] - 1});
    }

    // ps(s1);

    vector<int> ans;
    for (int i = 0; i + m <= n; ++i) {
        bool ok = true;

        for (auto it1 = s.begin(), it2 = s1.begin(); it1 != s.end(); it1++, it2++) {
            if (it1->s - i != it2->s) {
                ok = false;
                break;
            }
        }

        if (ok) {
            ans.push_back(i);
        }

        s.erase({a[i], i});
        s.insert({a[i + m], i + m});
    }

    cout << ans.size() << endl;
    for (auto it : ans) {
        cout << it + 1 << ' ';
    }
    cout << endl;
}

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