Submission #394184

#	Time	Username	Problem	Language	Result	Execution time	Memory
394184		two_sides	Painting Walls (APIO20_paint)	C++17	100 / 100	1117 ms	14832 KiB

paint

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

using namespace std;

const int MAXM = 50005;

int minimumInstructions
(int N, int M, int K,
vector <int> C, vector <int> A,
vector <vector <int>> B) {
    vector <int> cnt(M);
    vector <vector <int>> D(K);
    for (int i = 0; i < M; i++)
        for (int j : B[i])
            D[j].push_back(i);
    int cur = 0;
    for (int i = 0; i + 1 < M; i++)
        for (int j : D[C[i]])
            cnt[(j - i % M + M) % M]++;
    vector <int> P;
    for (int i = M - 1; i < N; i++) {
        for (int j : D[C[i]])
            if (++cnt[(j - i % M + M) % M] == M)
                cur++;
        if (cur) P.push_back(i - M + 1);
        for (int j : D[C[i - M + 1]])
            if (cnt[(j - (i - M + 1) % M + M) % M]-- == M)
                cur--;
    }
    cur = 0; int res = 0;
    for (int i = 0; i < P.size(); ) {
        int nxt = -1;
        while (i < P.size() && P[i] <= cur)
            nxt = P[i++] + M;
        if (nxt < 0) break;
        res++; cur = nxt;
    }
    return cur < N ? -1 : res;
}

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:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < P.size(); ) {
      |                     ~~^~~~~~~~~~
paint.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         while (i < P.size() && P[i] <= cur)
      |                ~~^~~~~~~~~~

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