Submission #1342507

#TimeUsernameProblemLanguageResultExecution timeMemory
1342507dex111222333444555Matching (CEOI11_mat)C++20
92 / 100
710 ms50416 KiB
#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second
#define siz(v) (int)(v).size()
#define lli pair<long long, int>
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))

using namespace std;

const int MAXN = 1e6 + 6, infINT = 1e9 + 1321, mod = 1e9 + 7, base = 1e9 + 1;
const long long inf = 1e18 + 1231;

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

void sub(int &a, const int &b){
    a -= b;
    if (a < 0) a += mod;
}

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

int numValA, numValB, hashT, valA[MAXN], valB[MAXN], powB[MAXN], sumB;
vector<int > comp;

struct Node{
    int hashS, cnt;

    Node(int _hashS = 0, int _cnt = 0):
        hashS(_hashS), cnt(_cnt) {};

    Node operator +(const Node &other) const{
        Node res;
        res.hashS = mul(hashS, powB[other.cnt]);
        add(res.hashS, other.hashS);
        res.cnt = cnt + other.cnt;
        return res;
    }
};

struct segmentTree{
    int n;
    vector<Node > node;

    segmentTree(int _n = 0): n(_n){
        node.assign(n << 2 | 1, Node());
    }

    void update(int id, int l, int r, int pos, const Node &x){
        if (l > r) return;
        if (l == r){
            node[id] = x;
            return;
        }
        int m = (l + r) >> 1;
        if (pos <= m) update(id << 1, l, m, pos, x);
        else update(id << 1 | 1, m + 1, r, pos, x);
        node[id] = node[id << 1] + node[id << 1 | 1];
    }

    void update(int pos, const Node &x){
        update(1, 1, n, pos, x);
    }
};

void input(){
    cin >> numValA >> numValB;

    powB[0] = sumB = 1;
    for(int i = 1; i <= numValA; i++){
        powB[i] = mul(powB[i - 1], base);
        if (i < numValA) add(sumB, powB[i]);
        cin >> valA[i];
    }

    for(int i = 1; i <= numValB; i++){
        cin >> valB[i];
        comp.push_back(valB[i]);
    }
}

void solve(){
    sort(all(comp));
    comp.resize(unique(all(comp)) - begin(comp));

    for(int i = 1; i <= numValB; i++){
        valB[i] = lower_bound(all(comp), valB[i]) - begin(comp) + 1;
    }

    for(int i = 1; i <= numValA; i++){
        hashT = mul(hashT, base);
        add(hashT, valA[i]);
    }

    vector<int > ans;

    segmentTree it(numValB);
    for(int i = 1; i <= numValA; i++) it.update(valB[i], Node(i, 1));

    if (it.node[1].hashS == hashT) ans.push_back(1);

    for(int i = numValA + 1; i <= numValB; i++){
        it.update(valB[i - numValA], Node(0, 0));
        it.update(valB[i], Node(i, 1));
        add(hashT, sumB);
        if (it.node[1].hashS == hashT) ans.push_back(i - numValA + 1);
    }

    cout << siz(ans) << '\n';
    for(int x: ans) cout << x << ' '; cout << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    input();
    solve();
    cerr << (1.0 * clock()) / CLOCKS_PER_SEC << ".s\n";
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mat.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...