Submission #563422

#	Time	Username	Problem	Language	Result	Execution time	Memory
563422		8e7	Painting Walls (APIO20_paint)	C++17	40 / 100	237 ms	36584 KiB

paint

//Challenge: Accepted
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 400005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> f[maxn];
int n, m;
int zeros = 0;
int num[maxn];
int counter = 0;
void ch(int col, int ind, int d) {
	for (int i:f[col]) {
		int p = ((i - ind) % m + m)%m;
		if (num[p] == 0) zeros--;
		num[p] += d;
		if (num[p] == 0) zeros++;
	}
}
vector<int> pos;
bool poss[2 * maxn];
int to[19][2 * maxn];

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	counter++;
	assert(counter == 1);
	m = M;
	n = N;
	for (int i = 0;i < M;i++) {
		for (int j = 0;j < A[i];j++) {
			f[B[i][j]].push_back(i);
		}
	}
	for (int i = 0;i < N;i++) {
		C.push_back(C[i]);
	}
	for (int i = 0;i < m;i++) num[i] = m;
	for (int i = 0;i < m;i++) ch(C[i], i, -1);
	for (int i = 0;i < n;i++) {
		//debug(i, zeros);
		//pary(num, num + m);

		poss[i] = zeros > 0;	
		if (poss[i]) pos.push_back(i);
		ch(C[i], i, 1);
		ch(C[i+m], i+m, -1);
	}
	int ps = pos.size();
	for (int i = 0;i < ps;i++) pos.push_back(pos[i] + n);	
	for (int i:pos) {
		int ind = upper_bound(pos.begin(), pos.end(), i+m) - pos.begin() - 1;
		to[0][i] = pos[ind];
	}
	for (int i = 1;i < 19;i++) {
		for (int j = 0;j < 2 * n;j++) to[i][j] = to[i-1][to[i-1][j]]; 
	}
	int ret = 1<<30;
	for (int i = 0;i < n;i++) {
		if (poss[i]) {
			int cur = i, val = 0;
			for (int j = 18;j >= 0;j--) {
				if (to[j][cur] < i + n) {
					val += 1<<j;
					cur = to[j][cur];
				}
			}
			if (m == n) ret = 1;	
			else if (to[0][cur] >= i + n) {
				ret = min(ret, val + 1);	
			}
		}
	}
	if (ret > n) return -1;
	return ret;
}

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