Submission #714862

#	Time	Username	Problem	Language	Result	Execution time	Memory
714862		dxz05	Painting Walls (APIO20_paint)	C++17	100 / 100	1306 ms	262244 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    vector<vector<int>> painters(K);
    for (int i = 0; i < M; i++){
        for (int x : B[i]){
            painters[x].push_back(i);
        }
    }

    vector<vector<int>> from(M);

    for (int i = 0; i < N; i++){
        if (painters[C[i]].empty()) return -1;

        for (int j : painters[C[i]]){
            int x = ((j - i) % M + M) % M;
            from[x].push_back(i);
        }

    }

    vector<bool> can(N);
    for (int x = 0; x < M; x++){
        int sz = (int)from[x].size();

        for (int i = 0; i < sz; i++){
            int p1 = from[x][i];
            int p2 = p1 + M - 1;

            if (i + M - 1 < sz && from[x][i + M - 1] == p2){
                can[p1] = true;
            }
        }
    }

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

    vector<int> go;
    for (int i = 0; i < N; i++){
        if (can[i]) go.push_back(i);
    }

    int ans = 0;
    int i = 0;

    while (i < N){
        ans++;

        int p = upper_bound(go.begin(), go.end(), i) - go.begin() - 1;
        if (p < 0) return -1;

        int to = go[p] + M;
        if (to <= i) return -1;

        i = to;
    }

    return ans;
}

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