Submission #333581

#	Time	Username	Problem	Language	Result	Execution time	Memory
333581		alishahali1382	Painting Walls (APIO20_paint)	C++14	28 / 100	1564 ms	39436 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const int mod=1000000007;
const int MAXN=100010;

int n, m, k, x, y, ans;
int C[MAXN];
int dp[MAXN], F[MAXN];
vector<int> col[MAXN];
bool ok[2000][20001];

inline int is_bad(int c, int ins){
	return !ok[ins][c];
	int pos=lower_bound(all(col[ins]), c)-col[ins].begin();
	return (pos==col[ins].size() || col[ins][pos]!=c);
}

int minimumInstructions(int nn, int mm, int kk, vector<int> CC, vector<int> AA, vector<vector<int>> BB){
	n=nn;
	m=mm;
	for (int i=0; i<n; i++) C[i]=CC[i], F[i]=i;
	sort(all(CC));
	CC.resize(unique(all(CC))-CC.begin());
	k=min((int)CC.size()+1, kk);
	for (int i=0; i<n; i++) C[i]=lower_bound(all(CC), C[i])-CC.begin();
	
	for (int i=0; i<m; i++){
		col[i].resize(AA[i]);
		for (int j=0; j<AA[i]; j++){
			int tmp=lower_bound(all(CC), BB[i][j])-CC.begin();
			if (tmp==CC.size() || CC[tmp]!=BB[i][j]) col[i][j]=k-1;
			else col[i][j]=tmp;
			ok[i][col[i][j]]=1;
		}
		sort(all(col[i]));
	}
	
	
	for (int sh=0; sh<m; sh++){
		int bad=0;
		for (int i=0; i<n; i++){
			bad+=is_bad(C[i], (i+sh)%m);
			if (i>=m) bad-=is_bad(C[i-m], (i+sh)%m);
			if (i>=m-1 && bad==0) F[i]=min(F[i], i-m), debug(i);
			
		}
	}
	/*
	for (int x=0; x<m; x++) for (int y=0; y<=n-m; y++){
		bool bad=0;
		for (int l=y; l<y+m && !bad; l++) if (is_bad(C[l], (x+l)%m)) bad=1;
		if (bad) continue ;
		F[y+m-1]=min(F[y+m-1], y-1);
		debug2(y, y+m-1)
	}
	*/
	
	for (int i=n-2; ~i; i--) F[i]=min(F[i], F[i+1]);
	memset(dp, 63, sizeof(dp));
	for (int i=0; i<n; i++) if (F[i]!=i){
		if (F[i]==-1) dp[i]=1;
		else dp[i]=dp[F[i]]+1;
	}
	if (dp[n-1]>n) return -1;
	return dp[n-1];
}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4


*/

Compilation message (stderr)

paint.cpp: In function 'int is_bad(int, int)':
paint.cpp:28:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  return (pos==col[ins].size() || col[ins][pos]!=c);
      |          ~~~^~~~~~~~~~~~~~~~~
paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:44:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    if (tmp==CC.size() || CC[tmp]!=BB[i][j]) col[i][j]=k-1;
      |        ~~~^~~~~~~~~~~

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