Submission #1069355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069355		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) {
	map<int, int> use;	// contractor that uses color i
	for (int i = 0; i < M; i++) {
		use[B[i][0]] = i;
	}
	vector<bool> cfill(N - M + 1, false);
	for (int i = 0; i < N - M + 1; i++) {
		int r = i + M - 1;
		// try all rotations
		if (use.find(C[i]) == use.end())
			continue;
		int j = use[C[i]];
//		cout<<i<<": "<<j<<endl;
		bool works = true;
		for (int k = 0; k < M; k++) {
			// use (k+j) mod M
			if (B[(k + j) % M][0] != 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);
	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;
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, vi, vi, std::vector<std::vector<int> >)':
paint.cpp:22:7: warning: unused variable 'r' [-Wunused-variable]
   22 |   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