Submission #434693

#	Time	Username	Problem	Language	Result	Execution time	Memory
434693		dqhungdl	Painting Walls (APIO20_paint)	C++17	40 / 100	1578 ms	78560 KiB

paint

#include "paint.h"

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

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

int dfs(int i,int j) {
	if(i==_N-1)
		return _N-1;
	if(f[i][j]!=-1)
		return f[i][j];
	int pos=lower_bound(g[i+1].begin(),g[i+1].end(),(g[i][j]+1)%_M)-g[i+1].begin();
	if(pos<g[i+1].size()&&g[i+1][pos]==(g[i][j]+1)%_M)
		return f[i][j]=dfs(i+1,pos);
	return f[i][j]=i;
}

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
	_N=N,_M=M;
	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(),-1);
	}
	vector<bool> canStart(N);
	for(int i=0;i<N;i++)
		for(int j=0;j<g[i].size();j++) {
			int far=dfs(i,j);
			if(far-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 dfs(int, int)':
paint.cpp:16:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  if(pos<g[i+1].size()&&g[i+1][pos]==(g[i][j]+1)%_M)
      |     ~~~^~~~~~~~~~~~~~
paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int j=0;j<g[i].size();j++) {
      |               ~^~~~~~~~~~~~

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