Submission #657357

#	Time	Username	Problem	Language	Result	Execution time	Memory
657357		600Mihnea	Painting Walls (APIO20_paint)	C++17	28 / 100	1593 ms	162468 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);
	
	assert((int) like.size() == m);
	assert((int) cntt_t_.size() == m);
	
	for (int i = 0; i < m; i++) {
		assert((int) like[i].size() == cntt_t_[i]);
		sort(like[i].begin(), like[i].end());
	}
	
	vector<int> cnt(m, 0);
	
	
	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;
	};
	
	function<void(int, int)> add_position = [&] (int i, int sgn) {
		for (int z = 0; z < m; z++) {
			/*
			0 -> z
			1 -> (z + 1) % m
			i -> (z + i) % m 
			*/
			int guy = (z + i) % m;
			if (do_like(guy, cwant[i])) {
				cnt[z] += sgn;
			}
		}
	};
	
	for (int i = 0; i < m; i++) {
		add_position(i, +1);
	}
	
	
	
	/*
		ok[y][w] = 1 if wall y can be painted by worker w
		eu vreau ok[y][x] & ok[y + 1][(x + 1) % n] & ... & ok[y + m - 1][(x + m - 1) % n]
				dp[y][x] = longest cyclical thing starting here that works
	*/
	
	vector<bool> isok(n * m, 0);
	vector<int> best(n * m, 0);
	
	vector<bool> act(k, 0);
		
	for (int w = 0; w < m; w++) {
		for (auto &col : like[w]) {
			act[col] = 1;
		}
		for (int i = 0; i < n; i++) {
			if (act[cwant[i]]) {
				isok[i * m + w] = 1;
			}
		}
		for (auto &col : like[w]) {
			act[col] = 0;
		}
	}
	
	for (int i = n - 1; i >= 0; i--) {
		for (int w = 0; w < m; w++) {
			if (isok[i * m + w]) {
				best[i * m + w] = 1;
				if (i + 1 < n) {
					best[i * m + w] += best[(i + 1) * m + (w + 1) % m];
				}
			}
		}
	}
	for (int i = 0; i < m; i++) {
		ok[0] |= (cnt[i] == m);
	}
	for (int l = 1; l <= n - m; l++) {
		int r = l + m - 1;
		add_position(r, +1);
		add_position(l - 1, -1);
		for (int i = 0; i < m; i++) {
			ok[l] |= (cnt[i] == m);
		}
	}
	for (int y = 0; y + m - 1 < n; y++) {
		for (int w = 0; w < m; w++) {
			if (best[y * m + w] >= m) {
				//ok[y] = 1;
			}
		}
	}	
	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: 13 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37