Submission #657368

#	Time	Username	Problem	Language	Result	Execution time	Memory
657368		600Mihnea	Painting Walls (APIO20_paint)	C++17	51 / 100	1568 ms	13284 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;
	};
	
	/*

	for i in colors:
		sol += nrofguysliking[color[i]]
	always put the mostliked color
	
	sum of nrofguysliking[color[i]]^2<=ct => 
	nrofguysliking[color[i]]<=sqrt(ct)

	*/
	
	vector<vector<int>> who(k);
	
	for (int guy = 0; guy < m; guy++) {
		for (auto &lk : like[guy]) {
			assert(0 <= lk && lk < k);
			who[lk].push_back(guy);
		}
	}
	
	
	function<void(int, int)> add_position = [&] (int i, int sgn) {
		for (auto &guy : who[cwant[i]]) {
			int z = (i + m - guy) % m;
			assert(0 <= z && z < m);
			cnt[z] += sgn;
		}
	};
	
	for (int i = 0; i < m; i++) {
		add_position(i, +1);
	}
	
	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);
		}
	}
	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: 23 / 23
• Subtask 5: 0 / 37