Submission #290709

#	Time	Username	Problem	Language	Result	Execution time	Memory
290709		TadijaSebez	Painting Walls (APIO20_paint)	C++11	100 / 100	981 ms	406868 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pb push_back

int minimumInstructions(int n,int m,int k,vector<int> c,vector<int> a,vector<vector<int>> b){
	vector<vector<int>> can(k);
	for(int i=0;i<m;i++)for(int j=0;j<a[i];j++)can[b[i][j]].pb(i);
	vector<vector<int>> pos(n+m);
	for(int i=0;i<n;i++){
		for(int j:can[c[i]]){
			pos[i+m-1-j].pb(i);
		}
	}
	vector<int> r(n,0),l(n,0);
	for(int z=0;z<n+m;z++){
		for(int j=0;j<pos[z].size();j++){
			if(pos[z][j]==z-m+1){
				int i=pos[z][j];
				while(j+r[i]<pos[z].size()&&pos[z][j+r[i]]==i+r[i])r[i]++;
			}
			if(pos[z][j]==z){
				int i=pos[z][j];
				while(j-l[i]>=0&&pos[z][j-l[i]]==i-l[i])l[i]++;
			}
		}
	}
	/*for(int i=0;i<n;i++){
		while(i+r[i]<n&&can[c[i+r[i]]].count(r[i]))r[i]++;
		while(i-l[i]>=0&&can[c[i-l[i]]].count(m-l[i]-1))l[i]++;
		//printf("%i %i %i\n",i,l[i],r[i]);
	}*/
	vector<bool> seg(n,0);
	vector<int> pre(n+1,0);
	for(int i=0;i<n-1;i++){
		if(l[i]+r[i+1]>=m){
			int sz=l[i]+r[i+1]-m+1;
			pre[i-l[i]+1]++;
			pre[i-l[i]+sz+1]--;
			//for(int j=1;j<=sz;j++)seg[i-l[i]+j]=1;
		}
	}
	for(int i=0,sum=0;i<n-1;i++){
		sum+=pre[i];
		if(sum>0)seg[i]=1;
	}
	if(l[n-1]==m)seg[n-m]=1;
	if(r[0]==m)seg[0]=1;
	vector<pii> ans;
	ans.pb({-1,-1});
	for(int i=0;i<n;i++){
		if(seg[i]){
			int sz=ans.size();
			if(sz>1&&ans[sz-2].second+1>=i)ans.pop_back();
			if(ans.back().second+1<i)return -1;
			ans.pb({i,i+m-1});
			//printf("%i %i\n",i,i+m-1);
		}
	}
	if(ans.back().second<n-1)return -1;
	return ans.size()-1;
}

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:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int j=0;j<pos[z].size();j++){
      |               ~^~~~~~~~~~~~~~
paint.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     while(j+r[i]<pos[z].size()&&pos[z][j+r[i]]==i+r[i])r[i]++;
      |           ~~~~~~^~~~~~~~~~~~~~

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