Submission #1069347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069347		pawned	Painting Walls (APIO20_paint)	C++17	0 / 100	0 ms	348 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<vector<bool>> use(M, vector<bool>(K, false));
	for (int i = 0; i < M; i++) {
		for (int x : B[i])
			use[i][x] = true;
	}
	vector<bool> cfill(N - M + 1, false);
	for (int i = 0; i < N - M + 1; i++) {
		int r = i + M - 1;
		// try all rotations
		for (int j = 0; j < M; j++) {	// offset
			bool works = true;
			for (int k = 0; k < M; k++) {
				// use (k+j) mod M
				if (!use[(k + j) % M][C[i + k]]) {
					works = false;
					break;
				}
			}
			if (works)
				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 - M + 1);
	int curr = -M;
	int total = 0;
	while (curr < N - M + 1) {
		auto it = good.lower_bound(curr + M + 1);
		if (it == good.begin())
			return false;
		int newc = *(--it);
		if (newc == curr)
			return false;
		curr = newc;
		total++;
	}
	total--;
	return total;
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, vi, vi, std::vector<std::vector<int> >)':
paint.cpp:23:7: warning: unused variable 'r' [-Wunused-variable]
   23 |   int r = i + M - 1;
      |       ^

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