Submission #1069374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069374		pawned	Painting Walls (APIO20_paint)	C++17	12 / 100	30 ms	13024 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) {
	vi use(K, -1);	// 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]] = i;
		}
	}
/*	cout<<"use: ";
	for (int x : use)
		cout<<x<<" ";
	cout<<endl;*/
	vi valr(N, -1);
	for (int i = 0; i < N; i++) {
		valr[i] = use[C[i]];
	}
	vi pfst(N + 1, 0);	// prefix sum of number of not -1's
	for (int i = 1; i <= N; i++) {
		pfst[i] = pfst[i - 1];
		if (valr[i - 1] != -1)
			pfst[i]++;
	}
/*	cout<<"valr: ";
	for (int x : valr)
		cout<<x<<" ";
	cout<<endl;
	cout<<"pfst: ";
	for (int x : pfst)
		cout<<x<<" ";
	cout<<endl;*/
	vi diff(N - 1, 0);
	vi is1(N - 1, 0);	// 1 if diff[i] is 1; 0 otherwise
	for (int i = 0; i < N - 1; i++) {
		if (valr[i] != -1 && valr[i + 1] != -1) {
			diff[i] = valr[i + 1] - valr[i];
			diff[i] %= M;
			diff[i] += M;
			diff[i] %= M;
			if (diff[i] == 1 || M == 1)
				is1[i] = 1;
		}
	}
/*	cout<<"diff: ";
	for (int x : diff)
		cout<<x<<" ";
	cout<<endl;*/
	vi pfs(N, 0);
	pfs[0] = 0;
	for (int i = 1; i < N; i++) {
		pfs[i] = pfs[i - 1] + is1[i - 1];
	}
/*	cout<<"pfs: ";
	for (int x : pfs)
		cout<<x<<" ";
	cout<<endl;*/
	vector<bool> cfill(N - M + 1, false);
	for (int i = 0; i < N - M + 1; i++) {
		if (pfst[i + M] - pfst[i] == M && pfs[i + M - 1] - pfs[i] == M - 1)
			cfill[i] = 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: 12 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37