Submission #1226035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226035		sokratisi	Painting Walls (APIO20_paint)	C++20	0 / 100	2 ms	4936 KiB

paint

#include "paint.h"
#include <vector>
#include <set>
#include <cstdio>

using namespace std;

set<int> coltoconst[100005];

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < a[i]; j++) coltoconst[b[i][j]].insert(i);
    }
    int init = 0;
    int ans = 0;
    bool okay = true;
    set<int> cur;
    // printf("here\n");
    cur = coltoconst[c[0]];
    for (int i = 1; i < n; i++) {
        // printf("%d here\n", i);
        set<int> tempcur;
        for (auto u: cur) {
            // printf("%d here\n", i);
            if (coltoconst[c[i]].find((u+i)%m) != coltoconst[c[i]].end()) tempcur.insert(u);
        }
        cur = tempcur;
        // printf("%d: ", i);
        // for (auto u: cur) printf ("%d ", u);
        // printf ("\n");
        // printf("%d here\n", i);
        if (cur.empty() || i == n-1) {
            if (i == n-1) i++;
            if (i - init < m || (cur.empty() && i == n)) {
                okay = false;
                break;
            }
            ans += (i-init-1)/m + 1;
            init = i;
            for (auto u: coltoconst[c[i]]) {
                if (u - i >= 0) cur.insert((u - i)%m);
                else cur.insert((u-i)%m + m);
            }
        }
        // printf("%d: ", i);
        // for (auto u: cur) printf ("%d ", u);
        // printf ("\n");
        // printf("%d here\n", i);

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

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