Submission #657372

#	Time	Username	Problem	Language	Result	Execution time	Memory
657372		600Mihnea	Painting Walls (APIO20_paint)	C++17	100 / 100	1079 ms	15220 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = (int) 1e9 + 7;

int minimumInstructions(int n, int m, int k, vector<int> cwant, vector<int> cntt_t_, vector<vector<int>> like) {
	vector<int> ok(n, 0);
	vector<int> cnt(m, 0);	
	vector<vector<int>> who(k);
	for (int guy = 0; guy < m; guy++) {
		for (auto &lk : like[guy]) {
			who[lk].push_back(guy);
		}
	}
	int cm = 0;
	function<void(int, int)> add_position = [&] (int i, int sgn) {
		for (auto &guy : who[cwant[i]]) {
			int z = (i + m - guy) % m;  
			cm -= (cnt[z] == m);
			cnt[z] += sgn;
			cm += (cnt[z] == m);
		}
	};
	for (int i = 0; i < m; i++) {
		add_position(i, +1);
	}
	ok[0] = (cm >= 1);
	for (int l = 1; l <= n - m; l++) {
		int r = l + m - 1;
		add_position(r, +1);
		add_position(l - 1, -1);
		ok[l] = (cm >= 1);
	}
	vector<int> inds;
	for (int i = 0; i < n; i++) {
		if (ok[i]) {
			inds.push_back(i);
		}
	}
	if (inds.empty()) {
		return -1;
	}
	if (inds[0] != 0 || inds.back() != n - m) {
		return -1;	
	}
	int l = 0, cost = 0;
	while (1) {
		int r = l;
		cost++;
		while (r + 1 < (int) inds.size() && inds[r + 1] <= inds[l] + m) {
			r++;
		}
		if (r == (int) inds.size() - 1) {
			if (l < r) {
				cost++;
			}
			break;
		}
		if (l == r) {
			return -1;	
		}
		l = r;
	}
	return cost;
}

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37