Submission #511664

#	Time	Username	Problem	Language	Result	Execution time	Memory
511664		blue	Matching (CEOI11_mat)	C++17	18 / 100	2099 ms	65536 KiB

mat

#include <iostream>
#include <vector>
#include <set>
#include <map>
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 main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    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';


    // int final_ans = 0;
    vi final_ans;

    for(int v = 1; v <= m-n+1; v++)
    {
        // cerr << "v = " << v << '\n';
        vi ct_bit(1+m, 0);
        vi pow_bit(1+m, 0);

        int curr_hash = 0;

        for(int i = 1; i <= n; i++)
        {
            // cerr << "   i = " << i << '\n';
                        // cerr << "chk\n";
            // cerr << i << ' ' << v << ' '
            for(int j = h[i+v-1]; j <= m; j += j&-j)
                ct_bit[j]++;

            for(int j = h[i+v-1]; j <= m; j += j&-j)
                pow_bit[j] = ad(pow_bit[j], powbs[m-i]);


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

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

        // final_ans += (curr_hash == s_hash);
        // cerr << "done\n";

        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: 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