Submission #474234

#	Time	Username	Problem	Language	Result	Execution time	Memory
474234		JovanB	Painting Walls (APIO20_paint)	C++17	100 / 100	1224 ms	14660 KiB

paint

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

using ll = long long;
using ld = long double;

const int N = 100000;

vector <int> voli[N+5];
int ima[N+5];
int cnt;

int minimumInstructions(int _n, int _m, int K, vector <int> C, vector <int> A, vector <vector <int>> B) {
    int n = _n;
    int m = _m;
    for(int i=0; i<m; i++){
        for(int j=0; j<A[i]; j++){
            voli[B[i][j]].push_back(i);
        }
    }
    vector <int> vec;
    for(int i=0; i<n; i++){
        if(i >= m){
            for(auto x : voli[C[i-m]]){
                int h = i - m - x;
                if(h < 0) h += m;
                h %= m;
                if(ima[h] == m) cnt--;
                ima[h]--;
            }
        }
        for(auto x : voli[C[i]]){
            int h = i - x;
            if(h < 0) h += m;
            h %= m;
            ima[h]++;
            if(ima[h] == m) cnt++;
        }
        if(cnt) vec.push_back(i - m + 1);
    }
    if(vec.empty() || vec[0] != 0 || vec.back() != n - m) return -1;
    int lst = 0;
    int res = 1;
    while(lst + 1 != vec.size()){
        res++;
        int x = lst;
        while(x + 1 < vec.size() && vec[x+1] <= vec[lst] + m) x++;
        if(x == lst) return -1;
        lst = x;
    }
    return 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:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while(lst + 1 != vec.size()){
      |           ~~~~~~~~^~~~~~~~~~~~~
paint.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         while(x + 1 < vec.size() && vec[x+1] <= vec[lst] + m) x++;
      |               ~~~~~~^~~~~~~~~~~~

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