Submission #372090

#	Time	Username	Problem	Language	Result	Execution time	Memory
372090		Cantfindme	Painting Walls (APIO20_paint)	C++17	100 / 100	813 ms	14728 KiB

paint

#include <bits/stdc++.h>
using namespace std;
//#define int long long
typedef long long ll;
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()

//int happy[100010];
deque <int> happy;
int range[100010];
vector <int> workers[100010];

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
		
	for (int i =0;i<M;i++) {
		for (auto j: B[i]) {
			workers[j].push_back(i);
		}
	}
	
	for (int path = 0;path<M;path++) happy.push_back(0);
	
	for (int wall =0;wall<M;wall++) {
		for (auto cur: workers[C[wall]]) {
			int path = (cur - wall + M) % M;
			happy[path]++;
		}
	}
	
	int allhappy = 0;
	for (int path = 0; path < M; path++) {
		if (happy[path] == M) allhappy++;
	}
	
	if (allhappy >= 1) range[0] = 1;
		
	for (int i =0;i<N-M;i++) {
		for (auto cur: workers[C[i]]) {
			if (happy[cur] == M) allhappy--;
			happy[cur]--;
		}
		
		int addwall = i + M;
		for (auto cur: workers[C[addwall]]) {
			happy[cur]++;
			if (happy[cur] == M) allhappy++;
		}
		
		if (allhappy >= 1) range[i+1] = 1;
		
		happy.push_front(happy.back());
		happy.pop_back();
	}
	
	int ans = 0;
	int best = -1;
	if (range[0]) best = 0;
	
	int cur = 0;
	while (cur < N) {
		if (best == -1) {
			return -1;
		}
		
		int start = best;
		best = -1;
		for (int x = cur; x < start+M;x++) {
			if (x+1 >=N) continue;
			if (range[x+1]) best = max(best,x+1);
		}
		ans++;
		cur = start + M;
	}
		
	return ans;
}

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