Submission #335607

#	Time	Username	Problem	Language	Result	Execution time	Memory
335607		Joshc	Lottery (CEOI18_lot)	C++11	100 / 100	1819 ms	8940 KiB

lot

#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int a[10001], order[101];
vector<int> ans[101];
vector<pair<int, int> > k;
vector<int> k2;

void add(int i, int m) {
    if (m > k2.back()) return;
    ans[lower_bound(k2.begin(), k2.end(), m)-k2.begin()][i]++;
}

int main() {
    int n, l, q, x;
    scanf("%d%d", &n, &l);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    scanf("%d", &q);
    for (int i=0; i<q; i++) {
        scanf("%d", &x);
        k.emplace_back(x, i);
        for (int j=0; j<=n-l+1; j++) ans[i].push_back(0);
    }
    sort(k.begin(), k.end());
    for (int i=0; i<q; i++) {
        order[k[i].second] = i;
        k2.push_back(k[i].first);
    }
    for (int dif=1; dif<=n-l; dif++) {
        int c = 0;
        for (int i=1; i<=l; i++) c += a[i] != a[i+dif];
        add(1, c);
        add(1+dif, c);
        for (int i=2; i<=n+1-dif-l; i++) {
            c -= a[i-1] != a[i+dif-1];
            c += a[i+l-1] != a[i+dif+l-1];
            add(i, c);
            add(i+dif, c);
        }
    }
    for (int i=1; i<q; i++) for (int j=1; j<=n-l+1; j++) ans[i][j] += ans[i-1][j];
    for (int i=0; i<q; i++) {
        for (int j=1; j<=n-l+1; j++) printf("%d ", ans[order[i]][j]);
        printf("\n");
    }
}

Compilation message (stderr)

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

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