Submission #320764

#	Time	Username	Problem	Language	Result	Execution time	Memory
320764		dolphingarlic	Lottery (CEOI18_lot)	C++14	100 / 100	1255 ms	12260 KiB

lot

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

int a[10000], pref[100][10000], ans[100][10000];
pair<int, int> k[100];

int main() {
	int n, l, q;
	scanf("%d %d", &n, &l);
	for (int i = 0; i < n; i++) scanf("%d", a + i);
	scanf("%d", &q);
	for (int i = 0; i < q; i++) {
		scanf("%d", &k[i].first);
		k[i].second = i;
	}
	sort(k, k + q);

	for (int dx = 1; dx <= n - l; dx++) {
		int diff = 0;
		for (int p = 0; p < l; p++) diff += (a[p] != a[dx + p]);
		int lb = lower_bound(k, k + q, make_pair(diff, -1)) - k;
		if (lb < q) pref[lb][0]++, pref[lb][dx]++;
		for (int i = 1; i <= n - l - dx; i++) {
			diff += (a[i + l - 1] != a[i + dx + l - 1]) - (a[i - 1] != a[i + dx - 1]);
			int lb = lower_bound(k, k + q, make_pair(diff, -1)) - k;
			if (lb < q) pref[lb][i]++, pref[lb][i + dx]++;
		}
	}
	for (int t = 0; t < q; t++) for (int i = 0; i <= n - l; i++) {
		if (t) pref[t][i] += pref[t - 1][i];
		ans[k[t].second][i] = pref[t][i];
	}
	for (int t = 0; t < q; t++) {
		for (int i = 0; i <= n - l; i++) printf("%d ", ans[t][i]);
		printf("\n");
	}
}

Compilation message (stderr)

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

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