Submission #347078

#	Time	Username	Problem	Language	Result	Execution time	Memory
347078		patrikpavic2	Painting Walls (APIO20_paint)	C++17	100 / 100	932 ms	14956 KiB

paint

#include "paint.h"

#include <vector>
#include <cstdio>
#include <cstring>

#define PB push_back

using namespace std;

typedef vector < int > vi;

const int N = 1e5 + 500;
const int INF = 0x3f3f3f3f;

int naz[N], cookie = 0, lst[N], sad[N], kol[N];
vi tko[N];

int minimumInstructions(int n, int m, int k, vi C, vi A, vector< vi > B) {
	for(int i = 0;i < m;i++)
		for(int x : B[i])
  			tko[x].PB(i);
	memset(lst, -1, sizeof(lst));
	for(int i = 0;i < n;i++){
		int dob = 0;
		for(int x : tko[C[i]]){
			int koj = ((x - i + m) % m + m) % m;
			if(lst[koj] != i - 1)
				kol[koj] = 0;
			lst[koj] = i; kol[koj]++;
		//	printf("kol[ %d ] = %d\n", koj, kol[koj]);
			dob |= (kol[koj] >= m);
		}
		if(dob){
			naz[i - m + 1] = 1;
		}
	}
	int cur = 0, ans = 0, lst = 0, dsn = 0;
	for(;cur < n;){
		for(;lst <= cur;lst++)
			if(naz[lst])
				dsn = max(dsn, lst + m);
		//printf("cur = %d dsn = %d lst = %d\n", cur, dsn, lst);
		if(dsn <= cur)
			return -1;
		cur = dsn; ans++;
	}
	return ans;
}

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