Submission #403542

#	Time	Username	Problem	Language	Result	Execution time	Memory
403542		sealnot123	Painting Walls (APIO20_paint)	C++14	100 / 100	690 ms	15508 KiB

paint

#include "paint.h"

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define ROF(i,a,b) for(int i=(a); i>=(b); --i)
#define pb push_back
#define eb emplace_back
#define SZ(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define make_unique(a) sort(all((a))), (a).erase(unique(all((a))),(a).end())
#define x first
#define y second
#define MP make_pair
#define MT make_tuple
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) FOR(i,1,y) cout << "##"; cout << #x << " = " << x << endl

using namespace std;

typedef long long i64;
typedef tuple<int,int,int> iii;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long double ld;

int minimumInstructions(
    int N, int M, int K, vector<int> C,
    vector<int> A, vector<vector<int>> B) {

	vi bef(M), aft(M);
	vector<vi> color(K);

	FOR(i, 0, M-1){
		bef[i] = (i-1+M)%M;
		aft[i] = (i+1)%M;
		for(const int c : B[i]){
			color[c].eb(i);
		}
	}

	vi last(M,0);
	vi good;
	
	FOR(i, 0, N-1){
		int mx = 0;
		vector<pii> wait;
		for(const int c : color[C[i]]){
			wait.eb(c, 1);
			if(last[bef[c]] == -1) continue;
			wait.back().y = last[bef[c]]+1;
		}
		if(i==0){
			FOR(j,0,M-1) last[j] = -1;
		}else{
			for(const int c : color[C[i-1]]){
				last[c] = -1;
			}
		}
		for(const pii e : wait){
			last[e.x] = e.y;
			mx = max(e.y,mx);
		}
		if(mx >= M) good.eb(i);
	}

	if(good.empty()) return -1;
	if(good.back() != N-1) return -1;

	deque<pair<int,int>> q;
	q.eb(-1, 0);
	for(const int e : good){
		//printf("good %d\n",e);
		while(!q.empty() && q.front().x < e-M) q.pop_front();
		if(q.empty()){
			return -1; // impossible
		}
		q.eb(e, q.front().y+1);
	}
  	return q.back().y;
}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4

5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3

1 1 10
0     
1 1   
*/

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