oj.uz

Submission #890699

# Submission time Handle Problem Language Result Execution time Memory
890699 2023-12-21T18:46:22 Z hct_2so1 Matching (CEOI11_mat) C++14
100 / 100
 888 ms 49484 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6616 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9060 KB Output is correct
2 Correct 11 ms 8784 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 15052 KB Output is correct
2 Correct 107 ms 14804 KB Output is correct
3 Correct 138 ms 18096 KB Output is correct
4 Correct 144 ms 17864 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 17616 KB Output is correct
2 Correct 145 ms 15636 KB Output is correct
3 Correct 113 ms 15824 KB Output is correct
4 Correct 117 ms 16864 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 17900 KB Output is correct
2 Correct 102 ms 17356 KB Output is correct
3 Correct 124 ms 15560 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 43836 KB Output is correct
2 Correct 719 ms 49484 KB Output is correct
3 Correct 635 ms 36908 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 42944 KB Output is correct
2 Correct 888 ms 37644 KB Output is correct
3 Correct 696 ms 46264 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 42428 KB Output is correct
2 Correct 643 ms 48504 KB Output is correct
3 Correct 751 ms 42636 KB Output is correct
4 Correct 443 ms 47548 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 42588 KB Output is correct
2 Correct 737 ms 43192 KB Output is correct
3 Correct 276 ms 25348 KB Output is correct
4 Correct 540 ms 48056 KB Output is correct