Submission #217520

#	Time	Username	Problem	Language	Result	Execution time	Memory
217520		DystoriaX	Lottery (CEOI18_lot)	C++14	45 / 100	26 ms	640 KiB

lot

#include <bits/stdc++.h>

using namespace std;

int n, l;
int a[2010], b[2010];
int cnt[2010][2010];
int q, qr[110];
vector<int> cmp;

int main(){
    scanf("%d%d", &n, &l);

    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];

    scanf("%d", &q);

    for(int i = 1; i <= q; i++){
        scanf("%d", &qr[i]);

        cmp.emplace_back(qr[i]);
    }

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

    for(int d = 1; d < n - l + 1; d++){
        int diff = 0;

        for(int j = 1; j <= l; j++){
            if(a[j] != a[j + d]) diff++;
        }

        auto it = upper_bound(cmp.begin(), cmp.end(), diff - 1) - cmp.begin();
        cnt[it][1]++;
        cnt[it][d + 1]++;

        for(int i = 2; i + l + d - 1 <= n; i++){
            if(a[i - 1] != a[i + d - 1]) diff--;
            if(a[i + l - 1] != a[i + l - 1 + d]) diff++;

            // cout << "Comparing " << i + l - 1 << " with " << i + l + d - 

            it = upper_bound(cmp.begin(), cmp.end(), diff - 1) - cmp.begin();
            cnt[it][i]++;
            cnt[it][i + d]++;
        }
    }

    for(int i = 1; i <= n; i++){
        for(int k = 1; k <= q; k++)
            cnt[k][i] += cnt[k - 1][i];
    }

    for(int i = 1; i <= q; i++){
        auto it = upper_bound(cmp.begin(), cmp.end(), qr[i] - 1) - cmp.begin();
        for(int j = 1; j <= n - l + 1; j++){
            printf("%d ", cnt[it][j]);
        }
        printf("\n");
    }
    
    return 0;
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &l);
     ~~~~~^~~~~~~~~~~~~~~~
lot.cpp:14:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
                                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
lot.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
lot.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &qr[i]);
         ~~~~~^~~~~~~~~~~~~~

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