Submission #730684

#	Time	Username	Problem	Language	Result	Execution time	Memory
730684		t6twotwo	Painting Walls (APIO20_paint)	C++17	0 / 100	1583 ms	212 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int inf = 1E6;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    vector<vector<int>> f(K);
    for (int i = 0; i < M; i++) {
        for (int x : B[i]) {
            f[x].push_back(i);
        }
    }
    int good = 0;
    vector<int> cnt(M);
    auto add = [&](int x) {
        for (int y : f[C[x]]) {
            if (++cnt[((y - x) % M + M) % M] == M) {
                good++;
            }
        }
    };
    auto rem = [&](int x) {
        for (int y : f[C[x]]) {
            if (cnt[((y - x) % M + M) % M]-- == M) {
                good--;
            }
        }
    };
    for (int i = 0; i < M; i++) {
        add(i);
    }
    vector<int> b;
    for (int i = M; i <= N; i++) {
        if (good) {
            b.push_back(i - 1);
        }
        if (i == N) {
            break;
        }
        rem(i - M);
        add(i);
    }
    int ans = 0;
    for (int i = -1, j = 0; i < N - 1; ans++) {
        while (j + 1 < b.size() && b[j + 1] <= i + M) {
            j++;
        }
        if (j == b.size() || b[j] > i + M) {
            return -1;
        }
        i = b[j];
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         while (j + 1 < b.size() && b[j + 1] <= i + M) {
      |                ~~~~~~^~~~~~~~~~
paint.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |         if (j == b.size() || b[j] > i + M) {
      |             ~~^~~~~~~~~~~

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