Submission #1251348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251348		minhpk	Lottery (CEOI18_lot)	C++20	25 / 100	1148 ms	86832 KiB

lot

#include <bits/stdc++.h>
using namespace std;

int a, b, q;
int z[1000005];
vector<unordered_map<int, short>> f;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> b;
    for (int i = 1; i <= a; i++) {
        cin >> z[i];
    }

    f.resize(a - b + 2);

    for (int i = 2; i + b - 1 <= a; i++) {
        int sta = 1, sta1 = i;
        int cur = 0;
        for (int j = 0; j < b; j++) {
            if (z[j + sta] != z[j + sta1]) cur++;
        }
        f[sta][cur]++;
        f[sta1][cur]++;
        for (int j = i + b; j <= a; j++) {
            if (z[sta] != z[sta1]) cur--;
            sta++;
            sta1++;
            if (z[sta + b - 1] != z[sta1 + b - 1]) cur++;
            f[sta][cur]++;
            f[sta1][cur]++;
        }
    }

    vector<vector<short>> prefix(a - b + 2, vector<short>(b + 1, 0));
    for (int i = 1; i <= a - b + 1; i++) {
        for (int j = 0; j <= b; j++) {
            prefix[i][j] = (j > 0 ? prefix[i][j - 1] : 0) + f[i][j];
        }
    }

    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        for (int i = 1; i <= a - b + 1; i++) {
            cout << prefix[i][x] << " ";
        }
        cout << "\n";
    }
    return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20