Submission #1251361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251361		minhpk	Lottery (CEOI18_lot)	C++20	45 / 100	396 ms	131072 KiB

lot

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

int a, b;
int z[10005];
short res[10005];
vector<pair<short, short>> v;
pair<short, short> q[105];
vector<int> ans[105];
bool cmp(pair<short, short> a, pair<short, short> b) {
    return a.second < b.second;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i = 1; i <= a; i++) {
        cin >> z[i];
    }

    if ( ((a-b+1)*b) <= 5000000) {
        vector<vector<short>> f(a - b + 2, vector<short>(b + 1));
        for (int i = 2; i + b - 1 <= a; i++) {
            int sta = 1, sta1 = i, 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]++;
            }
        }
        for (int i = 1; i <= a - b + 1; i++) {
            for (int j = 1; j <= b; j++) {
                f[i][j] += f[i][j - 1];
            }
        }
        int q;
        cin >> q;
        while (q--) {
            int x;
            cin >> x;
            for (int i = 1; i <= a - b + 1; i++) {
                cout << f[i][x] << " ";
            }
            cout << "\n";
        }
    } else {
        v.clear();
        for (int i = 2; i + b - 1 <= a; i++) {
            int sta = 1, sta1 = i, cur = 0;
            for (int j = 0; j < b; j++) {
                if (z[j + sta] != z[j + sta1]) cur++;
            }
            v.push_back({sta, cur});
            v.push_back({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++;
                v.push_back({sta, cur});
                v.push_back({sta1, cur});
            }
        }

        sort(v.begin(), v.end(), cmp);

        int c;
        cin >> c;
        for (int i = 1; i <= c; i++) {
            cin >> q[i].first;
            q[i].second = i;
        }
        sort(q + 1, q + 1 + c);

        memset(res, 0, sizeof res);
        int cur = 0;
        for (int i = 1; i <= c; i++) {
            auto [x, id] = q[i];
            while (cur < v.size() && v[cur].second <= x) {
                res[v[cur].first]++;
                cur++;
            }
            for (int j = 1; j <= a - b + 1; j++) {
                ans[id].push_back(res[j]);
            }
        }

        for (int i = 1; i <= c; i++) {
            for (auto val : ans[i]) cout << val << " ";
            cout << "\n";
        }
    }
    return 0;
}

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