Submission #290698

#	Time	Username	Problem	Language	Result	Execution time	Memory
290698		TadijaSebez	Painting Walls (APIO20_paint)	C++11	63 / 100	1576 ms	17600 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<set<int>> can(k);
	for(int i=0;i<m;i++)for(int j=0;j<a[i];j++)can[b[i][j]].insert(i);
	vector<int> r(n,0),l(n,0);
	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;
}

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