Submission #1106165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106165		vladilius	Painting Walls (APIO20_paint)	C++17	0 / 100	360 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

int minimumInstructions(int n, int m, int k, vector<int> x, vector<int> A, vector<vector<int>> B){
    vector<vector<bool>> f(m, vector<bool>(k));
    for (int i = 0; i < m; i++){
        for (int j: B[i]){
            f[i][j] = 1;
        }
    }
    vector<int> T[n];
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if (f[j][x[i]]){
                T[i].pb(j);
            }
        }
        int q = (int) T[i].size();
        for (int j = 0; j < q; j++){
            T[i].pb(T[i][j] + m);
        }
        
        for (int j = 0; j < T[i].size(); j++) T[i][j] -= i;
    }
    
    map<int, vector<int>> mp;
    for (int i = 0; i < n; i++){
        for (int j: T[i]){
            mp[j].pb(i);
        }
    }
    
    vector<bool> gd(n);
    
    for (auto [y, V]: mp){
        int pre = 0;
        for (int i = 1; i < V.size(); i++){
            if (V[i] != (V[i - 1] + 1)){
                for (int j = V[pre]; j <= V[i - 1] - m + 1; j++) gd[j] = 1;
                pre = i;
            }
        }
        for (int j = V[pre]; j <= V.back() - m + 1; j++) gd[j] = 1;
    }
    
    int mx = -1, t = 0, 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:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int j = 0; j < T[i].size(); j++) T[i][j] -= i;
      |                         ~~^~~~~~~~~~~~~
paint.cpp:42:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int i = 1; i < V.size(); i++){
      |                         ~~^~~~~~~~~~

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