Submission #94424

#	Time	Username	Problem	Language	Result	Execution time	Memory
94424		Noam527	Lottery (CEOI18_lot)	C++17	100 / 100	599 ms	8188 KiB

lot

#include <bits/stdc++.h>
#include <unordered_set>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;

void debug(string names) {
	cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
	int pos = 0;
	for (; pos < names.size() && names[pos] != ' '  && names[pos] != ','; pos++)
		cout << names[pos];
	cout << ": " << par << "  ";
	while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
		pos++;
	}
	names.erase(names.begin(), names.begin() + pos);
	debug(names, left...);
}

int n, l, q;
vector<int> a;
vector<pair<int, int>> k;
vector<int> to;
int ans[101][10001] = {};



int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> l;
	a.resize(n);
	for (auto &i : a) cin >> i;
	cin >> q;
	k.resize(q);
	for (int i = 0; i < q; i++) cin >> k[i].first, k[i].second = i;
	sort(k.begin(), k.end());
	to.resize(l + 1);
	to[l] = q;
	int nxt = q - 1;
	while (nxt >= 0 && l == k[nxt].first) to[l]--, nxt--;
	for (int i = l - 1; i >= 0; i--) {
		to[i] = to[i + 1];
		while (nxt >= 0 && i == k[nxt].first) to[i]--, nxt--;
	}
//	cout << "to: ";
//	for (const auto &i : to) cout << i << " "; cout << '\n';

	int dist;
	for (int d = 1; d + l - 1 < n; d++) {
		dist = 0;
		for (int i = 0; i < l; i++)
			if (a[i] != a[i + d]) dist++;
		ans[to[dist]][0]++;
		ans[to[dist]][d]++;
		for (int i = 1; i + d + l - 1 < n; i++) {
			if (a[i - 1] != a[i + d - 1]) dist--;
			if (a[i + l - 1] != a[i + d + l - 1]) dist++;
			ans[to[dist]][i]++;
			ans[to[dist]][i + d]++;
		}
	}
	for (int i = 1; i < q; i++) for (int j = 0; j < n; j++) ans[i][j] += ans[i - 1][j];
	for (int i = 0; i < q; i++) k[i].first = i, swap(k[i].first, k[i].second);
	sort(k.begin(), k.end());
	for (auto &i : k) {
		for (int j = 0; j < n - l + 1; j++)
			cout << ans[i.second][j] << " ";
		cout << '\n';
	}
}

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