Submission #347375

#	Time	Username	Problem	Language	Result	Execution time	Memory
347375		jesus_coconut	Matching (CEOI11_mat)	C++17	100 / 100	1404 ms	65536 KiB

mat

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace __gnu_pbds;
using namespace std;

template<class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using ll = long long;

int const MOD = 1e9 + 7;
ll const baza = 997;

ll potf(ll n, int k) {
    ll ret = 1;
    while (k) {
        if (k % 2) {
            ret *= n;
            ret %= MOD;
        }
        n *= n;
        n %= MOD;
        k /= 2;
    }
    return ret;
}

template<class T>
struct BIT{
	vector<T> bit;

	explicit BIT(int N) : bit(N, 0) {}

	void add(int pos, T val) {
		for (; pos < (int) bit.size(); pos += pos & -pos) {
			bit[pos] += val;
		    bit[pos] %= MOD;
		}
	}

	T sum(int r) {
		T res{};
		for (; r > 0; r -= r & -r) {
			res += bit[r];
			res %= MOD;
		}
		return res;
	}

	T sum(int l, int r) {
	    T ret = sum(r) - sum(l - 1);
	    ret %= MOD;
	    if (ret < 0) ret += MOD;
	    return ret;
	}
};

ll divmod(ll a, ll b) {
    return (a * potf(b, MOD - 2)) % MOD;
}

vector<int> v;

vector<ll> potinv, potreg, nxt, prv;
vector<int> ans, ord, ordb;

BIT<ll> bit(1);

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

    int n, m;
    cin >> n >> m;
    potinv.resize(m + 10);
    potreg.resize(m + 10);
    potreg[0] = 1;
    for (int i = 1; i < m + 10; ++i) {
        potreg[i] = (potreg[i - 1] * baza) % MOD;
    }
    potinv[0] = 1;
    ll divtmp = divmod(1, baza);
    for (int i = 1; i < m + 10; ++i) {
        potinv[i] = (potinv[i - 1] * divtmp) % MOD;
    }
    ll fh = 0;
    {
        vector<int> p(n);
        for (int i = 0; i < n; ++i) {
            int a;
            cin >> a;
            --a;
            p[a] = i + 1;
        }
        fh = 0;
        for (auto a : p) {
            fh *= baza;
            fh += a;
            fh %= MOD;
        }
    }
    v.resize(m);
    for (auto &a : v) cin >> a;
    vector<int> tmp = v;
    sort(begin(tmp), end(tmp));
    tmp.erase(unique(begin(tmp), end(tmp)), end(tmp));
    for (auto &a : v) {
        a = lower_bound(begin(tmp), end(tmp), a) - begin(tmp) + 1;
    }

    bit.bit.resize(m + 10, 0);
    ll pot = 1;
    for (int i = m - 1; i > m - n; --i) {
        bit.add(v[i], pot);
        pot *= baza;
        pot %= MOD;
    }
    nxt.resize(m + 10), prv.resize(m + 10);
    int divi = 0;
    for (int i = m - n; i >= 0; --i) {
        nxt[i] = (bit.sum(v[i] + 1, m + 9) * potinv[divi]) % MOD;
        bit.add(v[i + n - 1], -potreg[divi]);
        bit.add(v[i], pot);
        pot *= baza;
        pot %= MOD;
        divi++;
        prv[i + n - 1] = (bit.sum(v[i + n - 1] + 1, m + 9) * potinv[divi]) % MOD;
    }
    ll h = 0;
    {
        vector<int> fix(n);
        for (int i = 0; i < n; ++i) {
            fix[i] = v[i];
        }
        tmp = fix;
        sort(begin(tmp), end(tmp));
        tmp.erase(unique(begin(tmp), end(tmp)), end(tmp));

        for (auto &a : fix) {
            a = lower_bound(begin(tmp), end(tmp), a) - begin(tmp) + 1;
        }
        for (int i = 0; i < n; ++i) {
            h *= baza;
            h += fix[i];
            h %= MOD;
        }
    }
    tmp.clear();
    ord.resize(m), ordb.resize(m);
    bit.bit.assign(m + 10, 0);
    for (int i = m - 1; i > m - n; --i) {
        bit.add(v[i], 1);
    }
    for (int i = m - n; i >= 0; --i) {
        ord[i] = bit.sum(v[i]) + 1;
        bit.add(v[i], 1);
        bit.add(v[i + n - 1], -1);
    }
    bit.bit.assign(m + 10, 0);
    for (int i = 0; i < n - 1; ++i) {
        bit.add(v[i], 1);
    }
    for (int i = n - 1; i < m; ++i) {
        ordb[i] = bit.sum(v[i]) + 1;
        bit.add(v[i], 1);
        bit.add(v[i - n + 1], -1);
    }
    v.clear();

    ans.reserve(n / 2);
    if (fh == h) ans.push_back(0);
    ll rem = potreg[n - 1];
    for (int i = n; i < m; ++i) {
        h -= rem * ord[i - n];
        h %= MOD;
        h -= nxt[i - n];
        h %= MOD;
        h += prv[i];
        h %= MOD;
        if (h < 0) h += MOD;
        h *= baza;
        h += ordb[i];
        h %= MOD;
        if (h < 0) h += MOD;
        if (fh == h) {
            ans.push_back(i - n + 1);
        }
    }
    cout << ans.size() << '\n';
    for (auto a : ans) cout << a + 1 << ' ';

    return 0;
}

• 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