Submission #760928

#	Time	Username	Problem	Language	Result	Execution time	Memory
760928		MilosMilutinovic	Lottery (CEOI18_lot)	C++14	100 / 100	354 ms	8608 KiB

lot

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
const int Q = 1e2 + 10;
int n, d, q, a[N], k[N], f[N][Q], nxt[N], id[N];
int main() {
    scanf("%d%d", &n, &d);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &q);
    for (int i = 0; i <= n; i++)
        nxt[i] = -1;
    for (int i = 1; i <= q; i++)
        scanf("%d", &k[i]), nxt[k[i]] = k[i];
    for (int i = n - 1; i >= 0; i--)
        if (nxt[i] == -1)
            nxt[i] = nxt[i + 1];
    int pos = 0;
    for (int i = 0; i <= n; i++)
        if (nxt[i] == i)
            id[i] = ++pos;
    for (int l = 1; l + d - 1 <= n; l++) {
        int cnt = 0;
        for (int i = 1; i <= d; i++)
            cnt += (a[i] != a[l + i - 1]);
        for (int r = 1; l + (d - 1) + (r - 1) <= n; r++) {
            if (l + r - 1 != r && nxt[cnt] != -1) {
                f[r][id[nxt[cnt]]] += 1;
                f[l + r - 1][id[nxt[cnt]]] += 1;
            }
            cnt -= (a[l + r - 1] != a[r]);
            cnt += (a[l + r + d - 1] != a[r + d]);
        }
    }
    for (int i = 1; i <= q; i++) {
        for (int j = 1; j + d - 1 <= n; j++) {
            int cnt = 0;
            for (int x = 1; x <= id[k[i]]; x++)
                cnt += f[j][x];
            printf("%d ", cnt);
        }
        printf("\n");
    }
    return 0;
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:7:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     scanf("%d%d", &n, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~
lot.cpp:9:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
lot.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
lot.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d", &k[i]), nxt[k[i]] = k[i];
      |         ~~~~~^~~~~~~~~~~~~

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