Submission #576505

#	Time	Username	Problem	Language	Result	Execution time	Memory
576505		Arnch	Painting Walls (APIO20_paint)	C++17	100 / 100	755 ms	13296 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>

#define Sz(x) x.size()

using namespace std;

const int N = 1e5 + 10;

int dp[N], delta[N], cnt[N];
bool mark[N];
vector<int> vc[N];

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {

	for(int i = 0; i < Sz(B); i++) {
		for(auto j : B[i]) {
			vc[j].push_back(i);
		}
	}
	
	for(int i = 0; i < Sz(A); i++) delta[i] = -1, dp[i] = 0;

	vector<int> can, nc;
	for(int i = 0; i < Sz(C); i++) {
		can.clear(), nc.clear();
		if(Sz(vc[C[i]]) == 0) {
			return -1;
		}
		for(auto j : vc[C[i]]) {
			if(delta[(j - 1 + M) % M] == i - 1) {
				can.push_back(j);
			}
			else {
				nc.push_back(j);
			}
		}
		for(auto j : can) {
			delta[j] = i, cnt[j] = dp[(j - 1 + M) % M];
			if(cnt[j] < M) cnt[j]++;
		}
		for(auto j : can) {
			dp[j] = cnt[j];
			if(dp[j] == M) mark[i] = 1;
		}
		for(auto j : nc) {
			delta[j] = i, dp[j] = 1;
			if(dp[j] == M) mark[i] = 1;
		}
	}

	/*for(int i = 0; i < Sz(C); i++) {
		cout<<mark[i] <<" ";
	}
	cout<<endl;*/

	int ptr = Sz(C) - 1, ans = 1;
	if(mark[ptr] == 0) {
		return -1;
	}
	while(ptr >= M) {
		ans++;
		bool F = 0;
		for(int i = max(M - 1, ptr - M); i < ptr; i++) {
			if(mark[i]) {
				F = 1;
				ptr = i; break;
			}
		}
		if(!F) return -1;
	}
	
	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0; i < Sz(B); i++) {
      |                   ^
paint.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i = 0; i < Sz(A); i++) delta[i] = -1, dp[i] = 0;
      |                   ^
paint.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = 0; i < Sz(C); i++) {
      |                   ^

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