제출 #1285171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285171		dex111222333444555	Matching (CEOI11_mat)	C++20	100 / 100	731 ms	54328 KiB

mat

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
template<class X, class Y> bool maximize (X &x, const Y &y) {return x < y ? x = y, 1 : 0;}
template<class X, class Y> bool minimize (X &x, const Y &y) {return x > y ? x = y, 1 : 0;}
const int maxn = 1e6 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int base = 1e6 + 33;

struct nod{
    int fi, se;
    nod(int _fi = 0, int _se = 0): fi(_fi), se(_se) {};
};

int n, m;
int b[maxn], a[maxn];
int bpow[maxn];
vector<nod> st;

inline int mul(const int &a, const int &b) {return (1LL * a * b) % MOD;}

void add(int &a, const int &b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}

inline nod combine(const nod &a, const nod &b) {
    if (a.se == 0) return b;
    if (b.se == 0) return a;
    nod c;
    c.se = a.se + b.se;
    c.fi = mul(a.fi, bpow[b.se]);
    add(c.fi, b.fi);
    return c;
}

void upd(int id, int l, int r, int u, nod val)
{
    if (l == r)
    {
        st[id] = val;
        return ;
    }
    int mid = (l + r) >> 1;
    if (u <= mid) upd(id << 1, l, mid, u, val);
    else upd(id << 1 | 1, mid + 1, r, u, val);
    st[id] = combine(st[id << 1], st[id << 1 | 1]);
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //freopen(".INP", "r", stdin);
    //freopen(".OUT", "w", stdout);
    cin >> n >> m;


    int hsh = 0, up = 0;
    bpow[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    vector<int> comp;
    for (int i = 1; i <= m; ++i)
    {
        cin >> b[i];
        comp.pb(b[i]);
    }


    for (int i = 1; i <= n; ++i)
    {
        hsh = mul(hsh, base);
        add(hsh, a[i]);
        up = mul(up, base);
        add(up, 1);
    }

    sort(all(comp));
    for (int i = 1; i <= m; ++i)
    {
        b[i] = lower_bound(all(comp), b[i]) - comp.begin() + 1;
        bpow[i] = mul(bpow[i-1], base);
    }

    st.assign(m << 2 | 1, nod(0, 0));
    vector<int> ans;
    for (int i = 1; i <= m; ++i)
    {
        upd(1, 1, m, b[i], {i, 1});
        if (i > n) upd(1, 1, m, b[i-n], {0, 0});
        if (i >= n)
        {
            if (hsh == st[1].fi) ans.pb(i-n+1);
            add(hsh, up);
        }
    }
    cout << sz(ans) << '\n';
    for (auto i : ans) cout << i << ' ';
    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