Submission #409880

#	Time	Username	Problem	Language	Result	Execution time	Memory
409880		MohamedAhmed04	Painting Walls (APIO20_paint)	C++17	100 / 100	506 ms	262772 KiB

paint

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

using namespace std ;

const int MAX = 1e5 + 10 ;

int to[MAX] ;
int arr[MAX][633] ;

vector<int>v ;
vector<int>occ[MAX] ;

int minimumInstructions(
    int n, int m, int k, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) 
{
	v = C ;
	for(int i = 0 ; i < m ; ++i)
	{
		for(auto &j : B[i])
			occ[j].push_back(i) ;
	}
	for(int i = 0 ; i < k ; ++i)
		sort(occ[i].begin() , occ[i].end()) ;
	for(int i = 1 ; i < n ; ++i)
	{
		to[i] = i ;
		if(!occ[v[i]].size())
			return -1 ;
		int idx = 0 ;
		for(int j = 0 ; j < occ[v[i]].size() ; ++j)
		{
			arr[i][j] = i ;
			int x = occ[v[i]][j] ;
			if(!x)
				continue ;
			int prv = x-1 ;
			while(idx < occ[v[i-1]].size() && occ[v[i-1]][idx] < prv)
				idx++ ;
			if(idx == occ[v[i-1]].size())
				continue ;
			if(occ[v[i-1]][idx] != prv)
				continue ;
			arr[i][j] = arr[i-1][idx] ;
			to[arr[i][j]] = i ;
		}
		if(occ[v[i]][0] == 0)
		{
			int prv = m-1 ;
			while(idx < occ[v[i-1]].size() && occ[v[i-1]][idx] < prv)
				idx++ ;
			if(idx == occ[v[i-1]].size())
				continue ;
			if(occ[v[i-1]][idx] != prv)
				continue ;
			arr[i][0] = arr[i-1][idx] ;
			to[arr[i][0]] = i ;
		}
	}
	if(to[0] + 1 < m)
		return -1 ;
	int ans = 1 , now = m , nxt = -1 ;
	for(int i = 1 ; i < n ; ++i)
	{
		to[i] = max(to[i] , to[i-1]) ;
		if(to[i] + 1 >= i+m)
			nxt = i+m ;
		if(i == now)
		{
			ans++ ;
			if(nxt <= i && i != n-1)
				return -1 ;
			now = nxt ;
			nxt = -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:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int j = 0 ; j < occ[v[i]].size() ; ++j)
      |                   ~~^~~~~~~~~~~~~~~~~~
paint.cpp:40:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    while(idx < occ[v[i-1]].size() && occ[v[i-1]][idx] < prv)
      |          ~~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:42:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |    if(idx == occ[v[i-1]].size())
      |       ~~~~^~~~~~~~~~~~~~~~~~~~~
paint.cpp:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    while(idx < occ[v[i-1]].size() && occ[v[i-1]][idx] < prv)
      |          ~~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:54:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    if(idx == occ[v[i-1]].size())
      |       ~~~~^~~~~~~~~~~~~~~~~~~~~

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