Submission #1069357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069357		pawned	Painting Walls (APIO20_paint)	C++17	0 / 100	1567 ms	5884 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++) {
		for (int j = 0; j < A[i]; j++) {
			use[B[i][j]] = i;
		}
	}
	vector<bool> cfill(N - M + 1, false);
	for (int i = 0; i < N - M + 1; i++) {
		// 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 (use[C[i + k]] != ((k + j) % M)) {
				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;
}

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