Submission #830474

#	Time	Username	Problem	Language	Result	Execution time	Memory
830474		trytovoi	Matching (CEOI11_mat)	C++14	0 / 100	999 ms	64524 KiB

mat

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

#define REP(i, n) for(int i = 0, ____n = (n); i < ____n; ++i)
#define all(x) (x).begin(), (x).end()

const int MX = (int) 1e6 + 5;

const int NMOD = 2;
const int MOD[] = {127657753, 987654319};
const int BASE[] = {MX + 2, MX + 6};

void add(int& x, int y, int mod) {
    if ((x += y) >= mod) x -= mod;
}
int sadd(int x, int y, int mod) {
    add(x, y, mod);
    return x;
}
void sub(int& x, int y, int mod) {
    if ((x -= y) < 0) x += mod;
}
int ssub(int x, int y, int mod) {
    sub(x, y, mod);
    return x;
}

int n, m;
int a[MX], b[MX], c[MX];
int pw[MX][2], prefix[MX][2];

struct node {
    array<int, 2> val;
    int cnt;

    node(const array<int, 2>& _val = {0, 0}, int _cnt = 0) {
        val = _val;
        cnt = _cnt;
    }
} st[MX << 2];

node comb(const node& x, const node& y) {
    node res;
    res.cnt = x.cnt + y.cnt;
    REP(i, 2) res.val[i] = (x.val[i] + (1LL * pw[x.cnt][i] * y.val[i] % MOD[i])) % MOD[i];
    return res;
}

void update(int id, int l, int r, int p, int val) {
    if (r < p || l > p) return;
    if (l == r) {
        if (val == -1) {
            st[id].val = {0, 0};
            st[id].cnt = 0;
        }
        else {
            st[id].cnt = 1;
            st[id].val = {val % MOD[0], val % MOD[1]};
        }
        return;
    }

    int mid = (l + r) >> 1;
    int x = id << 1, y = x | 1;
    update(x, l, mid, p, val); update(y, mid + 1, r, p, val);
    st[id] = comb(st[x], st[y]);
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    pw[0][0] = pw[0][1] = 1;
    prefix[0][0] = prefix[0][1] = 1;
    for (int i = 1; i <= n; ++i) REP(j, NMOD) {
        pw[i][j] = 1LL * pw[i - 1][j] * BASE[j] % MOD[j];
        prefix[i][j] = sadd(prefix[i - 1][j], pw[i][j], MOD[j]);
    }
    array<int, 2> hashA = {0, 0};
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        c[a[i]] = i;
    }
    for (int i = 1; i <= n; ++i) REP(j, 2) add(hashA[j], 1LL * pw[i - 1][j] * c[i] % MOD[j], MOD[j]);
    vector<int> vec;
    for (int i = 1; i <= m; ++i) {
        cin >> b[i];
        vec.push_back(b[i]);
    }
    sort(all(vec));
    vec.resize(unique(all(vec)) - vec.begin());
    for (int i = 1; i <= m; ++i) 
        b[i] = lower_bound(all(vec), b[i]) - vec.begin() + 1;
    for (int i = 1; i <= n; ++i) update(1, 1, m, b[i], i);
    vector<int> ans;
    if (st[1].val == hashA) ans.push_back(1);
    for (int i = 2; i <= m - n + 1; ++i) {
        update(1, 1, m, b[i - 1], -1);
        update(1, 1, m, b[i + n - 1], i + n - 1);
        REP(j, 2) add(hashA[j], prefix[n - 1][j], MOD[j]);
        if (hashA == st[1].val) ans.push_back(i);
    }
    cout << (int) ans.size() << '\n';
    for (int x : ans) cout << x << ' ';
    return 0;
}

/**
6 12
2 5 3 4 1 6
10 45 25 30 5 47 31 35 4 50 33 20

5 1 3 4 2 6
BASE^0 * 5 + BASE^1 * 1 + BASE^2 * 3 + BASE^3 * 4 + BASE^4 * 2 + BASE^5 * 6

10 45 25 30 5 47
=> 5 1 3 4 2 6

5 6  7  8  9 10
5 47 31 35 4 50
=> 9 5 7 8 6 10
BASE^0 * 9 + BASE^1 * 5 + BASE^2 * 7 + BASE^3 * 8 + BASE^4 * 6 + BASE^5 * 10

**/

• Subtask 1: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 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