Submission #1106245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106245		vladilius	Painting Walls (APIO20_paint)	C++17	63 / 100	874 ms	524288 KiB

paint

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 3e5;

int minimumInstructions(int n, int m, int k, vector<int> x, vector<int> A, vector<vector<int>> B){
    vector<int> d[k];
    for (int i = 0; i < m; i++){
        for (int j: B[i]){
            d[j].pb(i);
        }
    }
    
    vector<int> V[inf];
    for (int i = 0; i < n; i++){
        for (int j: d[x[i]]){
            V[j + n - i].pb(i);
            V[(j + m) + n - i].pb(i);
        }
    }
    
    vector<bool> gd(n);
    for (int y = 0; y < inf; y++){
        int i = 0;
        while (i < V[y].size()){
            int j = i;
            while (j + 1 < V[y].size() && (V[y][j] + 1) == V[y][j + 1]) j++;
            for (int t = V[y][i]; t <= V[y][j] - m + 1; t++) gd[t] = 1;
            
            i = j + 1;
        }
    }
    
    int mx = -1, t = -1, out = 0;
    for (int i = 0; i < n; i++){
        if (gd[i]) t = max(t, i);
        if (i == (mx + 1)){
            if (t == -1) return -1;
            mx = t + m - 1;
            t = -1;
            out++;
        }
    }
    return out;
}

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:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         while (i < V[y].size()){
      |                ~~^~~~~~~~~~~~~
paint.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             while (j + 1 < V[y].size() && (V[y][j] + 1) == V[y][j + 1]) j++;
      |                    ~~~~~~^~~~~~~~~~~~~

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