oj.uz

Submission #511751

# Submission time Handle Problem Language Result Execution time Memory
511751 2022-01-16T04:17:06 Z blue Matching (CEOI11_mat) C++17
83 / 100
 2000 ms 65536 KB 
#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;

void add(vi& bit, int i, int v)
{
    for(int j = i; j <= m; j += j&-j)
        bit[j] = ad(bit[j], v);
}

int prefsum(vi& bit, int i)
{
    int res = 0;
    for(int j = i; j >= 1; j -= j&-j)
        res = ad(res, bit[j]);
    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+m, 0);

    int curr_hash = 0;

    for(int i = 1; i <= n; i++)
    {
        add(ct_bit, h[i], +1);

        add(pow_bit, h[i], powbs[m-i]);

        int curr_rank = 0;
        curr_rank += prefsum(ct_bit, h[i]-1);

        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);


        int nxt_rank = 0;

        nxt_rank = ad(nxt_rank, prefsum(ct_bit, h[v+n-1]-1));

        curr_hash = ad(curr_hash, nxt_rank);



        int disc = 0;
        disc = ad(disc, prefsum(pow_bit, m));
        disc = ad(disc, mod - prefsum(pow_bit, h[v-1]));

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

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

        curr_hash = ad(curr_hash, mod - disc);

        add(pow_bit, h[v-1], mod - powbs[m - (v-1)]);
        add(pow_bit, h[v+n-1], powbs[m - (v+n-1)]);


        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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 320 KB Output is correct
4 Correct 0 ms 308 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1600 KB Output is correct
2 Correct 10 ms 1480 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1576 KB Output is correct
2 Correct 11 ms 1612 KB Output is correct
3 Correct 4 ms 460 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 11628 KB Output is correct
2 Correct 108 ms 12864 KB Output is correct
3 Correct 321 ms 14404 KB Output is correct
4 Correct 268 ms 14460 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 12948 KB Output is correct
2 Correct 231 ms 14020 KB Output is correct
3 Correct 141 ms 13928 KB Output is correct
4 Correct 143 ms 14508 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 12776 KB Output is correct
2 Correct 119 ms 13508 KB Output is correct
3 Correct 141 ms 13672 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 939 ms 65272 KB Output is correct
2 Execution timed out 2086 ms 65536 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 898 ms 59752 KB Output is correct
2 Execution timed out 2039 ms 65536 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 900 ms 61872 KB Output is correct
2 Correct 808 ms 65536 KB Output is correct
3 Correct 1471 ms 65536 KB Output is correct
4 Correct 633 ms 65536 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 880 ms 62608 KB Output is correct
2 Correct 1119 ms 65536 KB Output is correct
3 Correct 285 ms 34220 KB Output is correct
4 Correct 850 ms 65536 KB Output is correct