Submission #1226097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226097		PanosPask	Painting Walls (APIO20_paint)	C++20	0 / 100	0 ms	324 KiB

paint

#include "paint.h"

#include <vector>
#include <queue>
#include <stack>

#define mp make_pair

using namespace std;

const int INF = 1e6;

typedef pair<int, int> pi;

// How few instructions to paint the first i days?
vector<int> dp;
vector<bool> doable;

bool find(vector<int>& v, int a) {
	int p = lower_bound(v.begin(), v.end(), a) - v.begin();
	if (p == v.size()) {
		return false;
	}

	return v[p] == a;
}

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	dp.assign(N + 1, INF);	
	doable.assign(N, false);

    vector<int> inv(K);
    for (int i = 0; i < N; i++) {
        inv[B[i][0]] = i;
    }

    queue<pi> res;
    res.push(mp(0, 0));

	for (int i = 0; i <= N - M; i++) {
        while (!res.empty() && res.front().first < i) {
            res.pop();
        }
        if (res.empty()) {
            return -1;
        }

        int p = res.front().second;

        int s = inv[C[i]];
        bool leave = false;
        for (int l = 0; l < M && !leave; l++) {
            int v = (l + s) % M;
            if (B[v][0] != C[l + i]) {
                i = i + l;
                leave = true;
                break;
            }
        }

        if (leave) {
            continue;
        }
        
        res.push(mp(i, p + 1));
    }

    while (!res.empty() && res.front().first < N) {
        res.pop();
    }
    if (res.empty()) {
        return -1;
    }
    else {
        return res.front().second;
    }
}

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