Submission #890699

#	Time	Username	Problem	Language	Result	Execution time	Memory
890699		hct_2so1	Matching (CEOI11_mat)	C++14	100 / 100	888 ms	49484 KiB

mat

#include <bits/stdc++.h>

#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define sz(v) ((ll) (v).size())
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define F first
#define S second
#define pii(x, y) make_pair(x, y)
#define __builtin_popcount __builtin_popcountll
#define __builtin_ctz __builtin_ctzll
#define __builtin_clz __builtin_clzll
#define lg(x) (63 - __builtin_clz(x))
#define task "array"

template <class X, class Y>
    bool minimize(X &x, const Y &y)
    {
        if (x > y) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y)
    {
        if (x < y) {x = y; return 1;}
        return 0;
    }

using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const int M = 2e6 + 5;
const int mod = 998244353;
const int base = 1e6 + 3;
const int INF = 1e9 + 7;
const ll oo = 2e18;

int n, m, HashS, adding, h[N], bit[N], st[4 * N], cnt[4 * N];
int pw[N];
vector<int> vi;

void Input(void)
{
    cin >> n >> m;
    pw[0] = 1;
    for (int i = 1; i <= n; i ++)
    {
        int s;
        cin >> s;
        pw[i] = 1LL * pw[i - 1] * base % mod;
        HashS = (1LL * HashS * base % mod + s) % mod;
        adding = (adding + pw[i - 1]) % mod;
    }
    for (int i = 1; i <= m; i ++) cin >> h[i], vi.push_back(h[i]);
    sort(all(vi));
    for (int i = 1; i <= m; i ++) h[i] = upper_bound(all(vi), h[i]) - vi.begin();
}

void update(int pos, int val, int id = 1, int l = 1, int r = m)
{
    if (l == r)
    {
        if (val == 0) st[id] = cnt[id] = 0;
        else st[id] = val, cnt[id] = 1;
        return ;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) update(pos, val, id * 2, l, mid);
    else update(pos, val, id * 2 + 1, mid + 1, r);
    st[id] = (1LL * st[id * 2] * pw[cnt[id * 2 + 1]] % mod + st[id * 2 + 1]) % mod;
    cnt[id] = cnt[id * 2] + cnt[id * 2 + 1];
}

void solve(void)
{
    for (int i = 1; i < n; i ++) update(h[i], i);
    vector<int> ans;
    for (int i = n; i <= m; i ++)
    {
        update(h[i], i);
        if ((st[1] + mod - 1LL * (i - n) * adding % mod) % mod == HashS) ans.push_back(i - n + 1);
        update(h[i - n + 1], 0);
    }
    cout << sz(ans) << '\n';
    for (int x : ans) cout << x << ' ';
}

int main()
{
    std::ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen(task ".INP", "r"))
        freopen(task ".INP", "r", stdin),
            freopen(task ".OUT", "w", stdout);
    int test = 1;
    //cin >> test;
    while (test --)
    {
        Input();
        solve();
    }
    return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(task ".INP", "r", stdin),
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mat.cpp:95:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |             freopen(task ".OUT", "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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