Submission #511842

#	Time	Username	Problem	Language	Result	Execution time	Memory
511842		blue	Matching (CEOI11_mat)	C++17	83 / 100	2053 ms	65536 KiB

mat

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cassert>
using namespace std;

using vi = vector<int>;
using ll = long long;
#define sz(x) int(x.size())

const ll mod = 1'000'000'007;
const int bs = 1'000'007;

int mul(ll a, ll b)
{
    return (a*b) % mod;
}

int ad(ll a, ll b)
{
    return (a+b)%mod;
}

int pow(int b, int e)
{
    int res = 1;

    while(e > 0)
    {
        if(e & 1)
        {
            res = mul(res, b);
            e ^= 1;
        }
        else
        {
            b = mul(b, b);
            e >>= 1;
        }
    }

    return res;
}

int inv(int a)
{
    return pow(a, mod-2);
}


int n, m;
vi ct_bit, pow_bit;

int pow_bit_sum = 0;

void add(vi& bit, int i, int v)
{
    for(int j = i; j <= (1<<20); j += j&-j)
        bit[j] = (bit[j]+v)%mod;
}

int prefsum(vi& bit, int i)
{
    int res = 0;
    for(int j = i; j >= 1; j ^= j&-j)
        res = (res+bit[j])%mod;
    return res;
}


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

    cin >> n >> m;

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




    vi h(1+m);
    map<int, int> hmap;

    for(int j = 1; j <= m; j++)
    {
        cin >> h[j];
        hmap[h[j]] = 0;
    }

    int hct = 0;
    for(auto& x: hmap) x.second = ++hct;
    for(int j = 1; j <= m; j++) h[j] = hmap[h[j]];

    hmap.clear();

    // for(int j = 1; j <= m; j++) cout << h[j] << ' ';
    // cout << '\n';
    // cerr << "check\n";

    // for(int q = 0; q < 20; q++) cerr << pow(2, q) << ' ' << pow(3, q) << '\n';

    int powbs[1+m];
    powbs[0] = 1;
    for(int e = 1; e <= m; e++) powbs[e] = mul(powbs[e-1], bs);

    int invbs[1+m];
    invbs[0] = 1;
    invbs[1] = inv(bs);
    for(int e = 2; e <= m; e++) invbs[e] = mul(invbs[e-1], invbs[1]);





    vi s_bit(1+n, 0);
    vi s_rank(1+n, 0);

    for(int i = 1; i <= n; i++)
    {
        for(int j = s[i]; j <= n; j += j&-j)
            s_bit[j]++;

        for(int j = s[i]-1; j >= 1; j -= j&-j)
            s_rank[s[i]] += s_bit[j];
    }

    int s_hash = 0;
    for(int i = 1; i <= n; i++) s_hash = ad(s_hash, mul(s_rank[i], powbs[n-i]));

    s_bit.clear();
    s_rank.clear();

    // cerr << "permutation ranks: ";
    // for(int i = 1; i <= n; i++) cerr << s_rank[i] << ' ';
    // cerr <<'\n';


    vi final_ans;

    // vi ct_bit(1+m, 0);
    // vi pow_bit(1+m, 0);
    ct_bit = pow_bit = vi((1<<20)+1, 0);

    int curr_hash = 0;

    for(int i = 1; i <= n; i++)
    {
        // add(ct_bit, h[i], +1);
        for(int j = h[i]; j <= m; j += j&-j)
            ct_bit[j]++;

        // add(pow_bit, h[i], powbs[m-i]);
        for(int j = h[i]; j <= m; j += j&-j)
            pow_bit[j] = (pow_bit[j] + powbs[m-i]) % mod;
        pow_bit_sum = ad(pow_bit_sum, powbs[m-i]);

        int curr_rank = 0;
        // curr_rank += prefsum(ct_bit, h[i]-1);
        for(int j = h[i]-1; j >= 1; j -= j&-j)
            curr_rank += ct_bit[j];

        curr_hash = ad(curr_hash, mul(curr_rank, powbs[n-i]));
    }

    if(curr_hash == s_hash)
        final_ans.push_back(1);

    // cerr << "initial hash = " << curr_hash << '\n';



    for(int v = 2; v <= m-n+1; v++)
    {
        curr_hash = mul(curr_hash, bs);

        // add(ct_bit, h[v-1], -1);
        // add(ct_bit, h[v+n-1], +1);
        for(int j = h[v-1]; j <= m; j += j&-j)
            ct_bit[j]--;
        for(int j = h[v+n-1]; j <= m; j += j&-j)
            ct_bit[j]++;


        int nxt_rank = 0;

        // nxt_rank = ad(nxt_rank, prefsum(ct_bit, h[v+n-1]-1));
        for(int j = h[v+n-1]-1; j >= 1; j -= j&-j)
            nxt_rank = (nxt_rank + ct_bit[j]) % mod;

        // curr_hash = ad(curr_hash, nxt_rank);
        curr_hash = (curr_hash + nxt_rank) % mod;



        int disc = 0;
        // disc = ad(disc, prefsum(pow_bit, m));
        disc = pow_bit_sum;
        // disc = ad(disc, mod - prefsum(pow_bit, h[v-1]));
        for(int j = h[v-1]; j >= 1; j -= j&-j)
            disc = (disc + mod - pow_bit[j]) % mod;

        int shft = v+n-2 - m + 1; //already shifted
        // assert(shft <= 0);

        disc = mul(disc, invbs[-shft]);

        // curr_hash = ad(curr_hash, mod - disc);
        curr_hash = (curr_hash + mod - disc) % mod;

        // add(pow_bit, h[v-1], mod - powbs[m - (v-1)]);
        // add(pow_bit, h[v+n-1], powbs[m - (v+n-1)]);
        for(int j = h[v-1]; j <= m; j += j&-j)
            pow_bit[j] = (pow_bit[j] + mod - powbs[m - (v-1)]) % mod;
        for(int j = h[v+n-1]; j <= m; j += j&-j)
            pow_bit[j] = ad(pow_bit[j], powbs[m - (v+n-1)]);

        // pow_bit_sum = ad(pow_bit_sum, mod - powbs[m - (v-1)]);
        // pow_bit_sum = ad(pow_bit_sum, powbs[m - (v+n-1)]);
        pow_bit_sum = (pow_bit_sum + mod - powbs[m - (v-1)]) % mod;
        pow_bit_sum = (pow_bit_sum + powbs[m - (v+n-1)]) % mod;

        if(curr_hash == s_hash)
            final_ans.push_back(v);
    }

    cout << sz(final_ans) << '\n';
    for(int v: final_ans) cout << v << ' ';
    cout << '\n';
}

• 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: 0 / 9
• Subtask 9: 0 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10