Submission #1282928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282928		altern23	Painting Walls (APIO20_paint)	C++20	0 / 100	1 ms	576 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

// Fixes for the screenshot-style approach
int minimumInstructions(int N,int M,int K,vector<int> C, vector<int> A, vector<vector<int>> B) {
    vector<vector<int>> mapping(K);
    for (int i = 0; i < M; ++i) {
        for (auto x : B[i]) mapping[x].push_back(i);
    }

    int ans = 0, last = -1, can = -1;
    vector<int> dp(M, 0);
    vector<int> vis(M, -1);            // initialize to -1 (not seen)

    for (int i = 0; i < N; ++i) {
        for (int x : mapping[C[i]]) {
            int idx = (x - i + M) % M; // use M in modulus and j - i
            if (vis[idx] != i) {       // not yet updated for this i
                dp[idx] = 0;           // reset
                vis[idx] = i;
            }
            if (++dp[idx] >= M) {
                can = i;
            }
        }

        if (i == N - 1 || i == last + M) {
            if (can == last) return -1;
            last = can;
            ans++;
        }
    }

    if (last != N - 1) return -1;
    return ans;
}

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