Submission #1201556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201556		shn	Painting Walls (APIO20_paint)	C++17	100 / 100	118 ms	18760 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A,vector<vector<int>> B){
	vector < int > g[K + 3] , d[N + 3];
	for(int i = 0; i < M; i++){
		for(int j = 0; j < A[i]; j++){
			// cout << i << ' ' << B[i][j] << '\n';
			g[B[i][j]].push_back(i);
		}
	}
	vector < pair < int , int > > v;
	int last[2][M];
	for(int i = 0; i < 2; i++){
		for(int j = 0; j < M; j++) last[i][j] = -2;
	}
	for(int i = 0; i < N; i++){
		if(i > 1){
			for(int it : g[C[i - 2]]){
				last[i & 1][it] = -2;
			}
		}
		bool ok = 0;
		for(int it : g[C[i]]){
			int prev = it - 1;
			if(prev == -1) prev = M - 1;
			if(last[(i & 1) ^ 1][prev] == -2) last[i & 1][it] = i - 1;
			else last[i & 1][it] = last[(i & 1) ^ 1][prev];
			if(last[i & 1][it] + M <= i && !ok){
				d[i - M + 1].push_back(i + 1);
				ok = 1;
				// cout << i - M + 1 << ' ' << i << '\n';
			}
			// cout << i << ' ' << it << ' ' << prev << ' ' << last[i & 1][it] << ' ' << last[i & 1][it] + M - 1 << '\n';
		}
	}
	int dst[N + 1];
	for(int i = 1; i <= N; i++){
		dst[i] = 1e9;
		d[i].push_back(i - 1);
	}
	dst[0] = 0;
	queue < int > q;
	q.push(0);
	while(q.size() > 0){
		int v = q.front();
		q.pop();
		for(int to : d[v]){
			if(to == v - 1){
				if(dst[to] > dst[v]){
					dst[to] = dst[v];
					q.push(to);
				}
			}
			else{
				if(dst[to] > dst[v] + 1){
					dst[to] = dst[v] + 1;
					q.push(to);
				}
			}
		}
	}
	if(dst[N] == 1e9) return -1;
	return dst[N];
}


// int main(){
	// int N , M , K;
	// cin >> N >> M >> K;
	// vector < int > C(N);
	// for(int i = 0; i < N; i++){
		// cin >> C[i];
	// }
	// vector < int > A(M);
	// vector < vector < int > > B(M);
	// for(int i = 0; i < M; i++){
		// cin >> A[i];
		// for(int j = 0; j < A[i]; j++){
			// int x;
			// cin >> x;
			// B[i].push_back(x);
		// }
	// }
	// cout << minimumInstructions(N , M , K , C , A , B);
// }

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