Submission #965908

#	Time	Username	Problem	Language	Result	Execution time	Memory
965908		pcc	Painting Walls (APIO20_paint)	C++17	28 / 100	1589 ms	154344 KiB

paint

#include "paint.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;

const int mxn = 1e5+10;
#define pii pair<int,int>
#define fs first
#define sc second
set<int> col[mxn];
bitset<mxn> able;
int N,M,K;
int arr[mxn];

bool check(int s){
	bool re = false;
	for(auto i:col[arr[s]]){
		int now = s;
		bool f = true;
		for(int j = 0;j<M;j++){
			if(col[arr[now]].find(i) == col[arr[now]].end()){
				f = false;
				break;
			}
			now++;
			i = (i+1)%M;
		}
		if(f)re = true;
	}
	return re;
}

namespace GRAPH{
	vector<int> paths[mxn];
	int dist[mxn];
	queue<int> q;
	void bfs(int s){
		memset(dist,-1,sizeof(dist));
		q.push(s);
		dist[s] = 0;
		while(!q.empty()){
			auto now = q.front();
			q.pop();
			for(auto nxt:paths[now]){
				if(dist[nxt] == -1){
					dist[nxt] = dist[now]+1;
					q.push(nxt);
				}
			}
		}
		return;
	}

	int GO(){
		for(int i = 0;i<N;i++){
			if(able[i]){
				for(int j = 1;j<=M;j++)paths[i].push_back(i+j);
			}
		}
		bfs(0);
		return dist[N];
	}
}

int minimumInstructions(
    int NN, int MM, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
	N = NN,M = MM;
	for(int i = 0;i<M;i++){
		for(int j = 0;j<A[i];j++)col[B[i][j]].insert(i);
	}
	for(int i = 0;i<N;i++)arr[i] = C[i];
	for(int i = 0;i+M<=N;i++)able[i] = check(i);
	return GRAPH::GO();
}

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