Submission #217522

#	Time	Username	Problem	Language	Result	Execution time	Memory
217522		DystoriaX	Lottery (CEOI18_lot)	C++14	100 / 100	816 ms	8464 KiB

lot

#include <bits/stdc++.h>

using namespace std;

int n, l;
int a[10010], b[10010];
int cnt[110][10010];
int q, qr[110];
int nxt[10010];
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());

    int idx = 0;
    for(int i = 0; i <= n; i++){
        while(idx < q && cmp[idx] < i) idx++;

        nxt[i] = idx;
    }

    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++;
        }

        cnt[nxt[diff]][1]++;
        cnt[nxt[diff]][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 - 

            cnt[nxt[diff]][i]++;
            cnt[nxt[diff]][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++){
        for(int j = 1; j <= n - l + 1; j++){
            printf("%d ", cnt[nxt[qr[i]]][j]);
        }
        printf("\n");
    }
    
    return 0;
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:13: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:15: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:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
lot.cpp:20: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: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20