Submission #290077

#	Time	Username	Problem	Language	Result	Execution time	Memory
290077		maximath_1	Painting Walls (APIO20_paint)	C++11	100 / 100	1186 ms	265092 KiB

paint

#include "paint.h"
#include <vector>
#include <set>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define vi vector<int>

vector<int> adj;
vector<bool> vis;
vector<int> up;
bool ada[100005];
vector<int> col[100005];
unordered_map<int, int> check[100005];
vector<int> cntt;
int minimumInstructions(int N, int M, int K, vi C, vi A, vector<vi> B){
	cntt.assign(K, 1);
	for(int i = 0; i < M; i ++)
		for(int j = 0; j < A[i]; j ++){
			col[B[i][j]].push_back(i);
			check[B[i][j]][i] = cntt[B[i][j]];
			cntt[B[i][j]] ++;
		}
	
	up.resize(N);

	int cnt = 0;
	for(int i = 0; i < N; i ++){
		cnt += col[C[i]].size();
		up[i] = cnt - 1;
	}

	adj.assign(cnt, -1);
	vis.assign(cnt, 0);

	for(int i = 0; i < N - 1; i ++){
		int gi = (i == 0 ? 0 : up[i - 1] + 1);
	//	for(int uwu = 0; uwu < M; uwu ++)
	//		cout << check[C[i + 1]][uwu] << " "; cout << endl;
		for(int j : col[C[i]]){ 
			int gt = check[C[i + 1]][(j + 1) % M];
	//		cout << gi << " " <<  gt << endl;
			if(gt){
				int gi2 = up[i] + gt;
				adj[gi] = gi2;
			//	cout << gi << " -> " << gi2 << endl;
			}
			gi ++;
		}
	}

	int tpnw = 0;
	for(int i = 0; i < cnt; i ++){
		if(up[tpnw] < i) tpnw ++;
		if(vis[i]) continue;
		int tp = tpnw;
		if(ada[tp]) continue;
		int len = 1;
		for(int nw = i;;){
			vis[nw] = 1;
			if(adj[nw] != -1){
				len ++;
				nw = adj[nw];
			}else break;
		}
	//	cout << i << " " << tp << " " << len << endl;
		for(int j = tp; j <= min(tp + len - M, N - 1); j ++)
			ada[j] = true;
	}

	if(!ada[0]) return -1;

	vector<int> pref(N);
	for(int i = 0; i < N; i ++){
		if(ada[i]) pref[i] = i;
		else if(i == 0) pref[i] = 0;
		else pref[i] = pref[i - 1];
	}

	int ans = 0; bool you = true;
	for(int cr = 0;;){
		ans ++;

		int nx = cr + M;
		if(nx == N) break;
		
		int id = pref[nx];
		if(id == cr){
			you = false; break;
		}
		cr = id;
	}

	if(!you) return -1;
	return ans;
}

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