Submission #1183268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183268		kayumov_muhammad	Matching (CEOI11_mat)	C++20	36 / 100	2094 ms	7752 KiB

mat

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target(."avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("Ofast")

#ifdef LOCAL
#include "debug/debug.hpp"
#else
#define print(...)
#endif

using ll = int;
using ld = double;
using ull = unsigned long long;
#define str string

#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define ent cout << "\n";
#define sz(v) ll(v.size())

using namespace std;

const long long MOD = 1e9 + 7, inf = 1e18;

void solve() {
    ll n, m;
    cin >> n >> m;

    ll a[n + 17];
    ll a2[n + 17];

    for (ll i = 1; i <= n; i++) {
        cin >> a2[i];
        a[a2[i]] = i;
    }

    ll b[m + 17];

    for (ll i = 1; i <= m; i++) {
        cin >> b[i];
    }
    vector<ll> ans;
    ll z[n + 17] = {};
    for (ll i = 1; i + n - 1 <= m; i++) {
        ll ok = 1;

        for (ll j = i; j - i + 1 <= n; j++) {
            z[a[j - i + 1]] = b[j];
            if (z[a[j - i + 1] - 1] != 0) {
                if (z[a[j - i + 1]] < z[a[j - i + 1] - 1]) {
                    ok = 0;
                    for (ll z1 = i; z1 <= j; z1++) {
                        z[a[z1 - i + 1]] = 0;
                    }
                    break;
                }
            }
            if (z[a[j - i + 1] + 1] != 0) {
                if (z[a[j - i + 1]] > z[a[j - i + 1] + 1]) {
                    ok = 0;
                    for (ll z1 = i; z1 <= j; z1++) {
                        z[a[z1 - i + 1]] = 0;
                    }
                    break;
                }
            }
        }
        if (ok)
            for (ll j = 1; j < n; j++) {
                if (z[j] > z[j + 1]) {
                    ok = 0;
                    for (ll z1 = i; z1 - i + 1 <= n; z1++) {
                        z[a[z1 - i + 1]] = 0;
                    }
                    break;
                }
            }
        if (ok) {
            ans.push_back(i);
            for (ll z1 = i; z1 - i + 1 <= n; z1++) {
                z[a[z1 - i + 1]] = 0;
            }
        }
        // print(t);
    }

    cout << sz(ans) << '\n';

    for (auto c : ans) {
        cout << c << ' ';
    }
    ent;
}

int32_t main() {
#ifdef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    ll ttest = 1;
    // cin >> ttest;

    for (ll test_number = 1; test_number <= ttest; test_number++) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

mat.cpp:4:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
    4 | #pragma GCC target(."avx2,bmi,bmi2,lzcnt,popcnt")
      |                    ^

• 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