제출 #940153

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
940153		vjudge1	Lottery (CEOI18_lot)	C++17	45 / 100	3028 ms	888 KiB

lot

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
	return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
	return a < b ? (a = b) == b : false;
}

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, l; cin >> n >> l;
	int a[n];
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	int q; cin >> q;
	vector<pair<int, int>> qri(q);
	for (int i = 0; i < q; ++i) {
		cin >> qri[i].first;
		qri[i].second = i;
	}
	sort(all(qri));
	int res[q][n];
	for (int i = 0; i + l - 1 < n; ++i) {
		deque<int> x, y;
		for (int j = i; j < i + l; ++j) {
			x.push_back(a[j]);
		}
		for (int j = 0; j < l; ++j) {
			y.push_back(a[j]);
		}
		int cnt = 0;
		for (int k = 0; k < l; ++k) {
			if (x[k] != y[k]) cnt++;
		}
		vector<int> v;
		if (i) v.push_back(cnt);
		for (int j = l; j < n; ++j) {
			y.pop_front();
			y.push_back(a[j]);
			if (j - l + 1 == i) continue;
			cnt = 0;
			for (int k = 0; k < l; ++k) {
				if (x[k] != y[k]) cnt++;
			}
			v.push_back(cnt);
		}
		sort(all(v));
		int s = 0, t = 0, add = 0;
		while (t < q) {
			while (s < size(v) && v[s] <= qri[t].first) {
				add++;
				s++;
			}
			res[qri[t].second][i] = add;
			t++;
		}
	}
	for (int i = 0; i < q; ++i) {
		for (int j = 0; j + l - 1 < n; ++j) {
			cout << res[i][j] << ' ';
		}
		cout << '\n';
	}
}

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