Submission #1069382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069382		pawned	Painting Walls (APIO20_paint)	C++17	51 / 100	205 ms	524288 KiB

paint

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "paint.h"

int minimumInstructions(int N, int M, int K, vi C, vi A, vector<vi> B) {
	vector<vi> use(K);	// use[i]: contractor who paints color i
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < A[i]; j++) {
			use[B[i][j]].pb(i);
		}
	}
/*	cout<<"use: ";
	for (int i = 0; i < K; i++) {
		cout<<i<<": ":
		for (int x : use[i])
			cout<<x<<" ";
		cout<<endl;
	}*/
	vector<vector<bool>> can(N, vector<bool>(M, false));
	for (int i = 0; i < N; i++) {
		for (int x : use[C[i]])
			can[i][x] = true;
	}
	vector<bool> cfill(N - M + 1, false);
	for (int i = 0; i < M; i++) {	// offset, start at i
		vector<bool> good(N, false);
		for (int j = 0; j < N; j++) {
			if (can[j][(i + j) % M])
				good[j] = true;
		}
		vi pfs(N + 1, 0);
		for (int j = 1; j <= N; j++) {
			pfs[j] = pfs[j - 1];
			if (good[j - 1])
				pfs[j]++;
		}
		for (int j = 0; j < N - M + 1; j++) {
			if (pfs[j + M] - pfs[j] == M)
				cfill[j] = true;
		}
	}
/*	cout<<"cfill: ";
	for (bool b : cfill)
		cout<<b<<" ";
	cout<<endl;*/
	set<int> good;
	for (int i = 0; i < N - M + 1; i++) {
		if (cfill[i])
			good.insert(i);
	}
	good.insert(-M);
	good.insert(N);
	int curr = -M;
	int total = 0;
	while (curr < N) {
		auto it = good.lower_bound(curr + M + 1);
		if (it == good.begin())
			return -1;
		int newc = *(--it);
		if (newc == curr)
			return -1;
		curr = newc;
		total++;
	}
	total--;
	return total;
}

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