Submission #657068

#	Time	Username	Problem	Language	Result	Execution time	Memory
657068		600Mihnea	Painting Walls (APIO20_paint)	C++17	15 / 100	1572 ms	1592 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> cnt, vector<vector<int>> like) {
	vector<bool> ok(n, 0);
	
	assert((int) like.size() == m);
	assert((int) cnt.size() == m);
	
	for (int i = 0; i < m; i++) {
		assert((int) like[i].size() == cnt[i]);
		sort(like[i].begin(), like[i].end());
	}
	
	function<int(int, int)> do_like = [&] (int i, int val) {
		int l = 0, r = (int) like[i].size() - 1;
		while (l <= r) {
			int m = (l + r) / 2;
			if (like[i][m] == val) {
				return 1;	
			}
			if (like[i][m] < val) {
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		return 0;
	};
	
	
	
	for (int y = 0; y + m - 1 < n; y++) {
		for (int x = 0; x < n; x++) {
			bool good = 1;
			for (int l = 0; l < m; l++) {
				good &= do_like((x + l) % m, cwant[y + l]);
			}
			if (good == 1) {
				ok[y] = 1;
				break;
			}
		}
	}	
	vector<int> inds;
	for (int i = 0; i < n; i++) {
		if (ok[i]) {
			inds.push_back(i);
		}
	}
	if (inds.empty()) {
		return -1;
	}
	assert((int) inds.size() >= 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: 0 / 12
• Subtask 2: 15 / 15
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37