Submission #434699

#	Time	Username	Problem	Language	Result	Execution time	Memory
434699		dqhungdl	Painting Walls (APIO20_paint)	C++17	100 / 100	868 ms	506324 KiB

paint

#include "paint.h"

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

const int MAX=1e5+5;
vector<int> companies[MAX],g[MAX],f[MAX];

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
	for(int i=0;i<M;i++)
		for(int j=0;j<A[i];j++)
			companies[B[i][j]].push_back(i);
	for(int i=0;i<N;i++) {
		g[i]=companies[C[i]];
		f[i].resize(g[i].size());
	}
	vector<bool> canStart(N);
	for(int i=0;i<g[N-1].size();i++)
		f[N-1][i]=N-1;
	for(int i=N-2;i>=0;i--) {
		int cur=0;
		for(int j=0;j<g[i].size();j++) {
			int nextValue=(g[i][j]+1)%M;
			if(nextValue==0)
				f[i][j]=(g[i+1].size()>0&&g[i+1][0]==0?f[i+1][0]:i);
			else {
				while(cur<g[i+1].size()&&g[i+1][cur]<nextValue)
					cur++;
				if(cur<g[i+1].size()&&g[i+1][cur]==nextValue)
					f[i][j]=f[i+1][cur];
				else
					f[i][j]=i;
			}
		}
	}
	for(int i=0;i<N;i++)
		for(int j=0;j<g[i].size();j++)
			if(f[i][j]-i+1>=M)
				canStart[i]=true;
	int cur=-1,lastPos=0,rs=0;
	while(lastPos<N) {
		int found=-1;
		for(int i=lastPos;i>cur;i--)
			if(canStart[i]) {
				found=i;
				break;
			}
		if(found==-1)
			return -1;
		lastPos=found+M;
		cur=found;
		rs++;
	}
	return rs;
}

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:20:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0;i<g[N-1].size();i++)
      |              ~^~~~~~~~~~~~~~
paint.cpp:24:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int j=0;j<g[i].size();j++) {
      |               ~^~~~~~~~~~~~
paint.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while(cur<g[i+1].size()&&g[i+1][cur]<nextValue)
      |           ~~~^~~~~~~~~~~~~~
paint.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     if(cur<g[i+1].size()&&g[i+1][cur]==nextValue)
      |        ~~~^~~~~~~~~~~~~~
paint.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int j=0;j<g[i].size();j++)
      |               ~^~~~~~~~~~~~

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