oj.uz

Submission #290686

# Submission time Handle Problem Language Result Execution time Memory
290686 2020-09-04T10:29:54 Z TadijaSebez Painting Walls (APIO20_paint) C++11
0 / 100
 0 ms 256 KB 
#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);
	for(int i=0;i<n-1;i++){
		if(l[i]+r[i+1]>=m){
			int sz=l[i]+r[i+1]-m+1;
			for(int j=1;j<=sz;j++)seg[i-l[i]+j]=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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -