Submission #553033

#	Time	Username	Problem	Language	Result	Execution time	Memory
553033		Itamar	Painting Walls (APIO20_paint)	C++14	40 / 100	1571 ms	35952 KiB

paint

#include "paint.h"

#include <cassert>
#include <cstdio>
#pragma warning(disable : 4996)
#include <map>
#include <iostream>
using namespace std;
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#define ll long long
#define vi vector<int> 
#define vll vector<ll>
#define pi pair<int,int> 
#define pll pair<ll,ll>

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {

    vector<vi> com(K);

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < A[i]; j++) {
            com[B[i][j]].push_back(i);
        }
    }
    vector<vi> kad(N);
    for (int i = 0; i < N; i++) {
        kad[i].resize(com[C[i]].size());
    }
    for (int i = N - 2; i >= 0; i--) {
        if (com[C[i]].empty())
            return -1;
        for (int j = 0; j < kad[i].size(); j++) {
            for (int k = 0; k < kad[i+1].size(); k++) {
                if (com[C[i + 1]][k] == (com[C[i]][j] + 1) % M) {
                    kad[i][j] = kad[i + 1][k] + 1;
                }
            }
        }
    }
    vector<bool> ket(N);
    for (int i = 0; i < N; i++) {
        for (int j : kad[i]) {
            if (j >= M - 1) {
                ket[i] = 1;
            }
        }
    }
    if (com[C[N - 1]].empty())
        return -1;
    int sum = 0;
    int last = -M;
    int need = 0;
    for (int i = 0; i < N; i++) {
        if (ket[i]) {
            last = i;
        }
        if (need ==i) {
            if (i - last >= M )
                return -1;
            sum++;
            need = last + M;
        }
    }
    return sum;
}

Compilation message (stderr)

paint.cpp:5: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    5 | #pragma warning(disable : 4996)
      | 
paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:37:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int j = 0; j < kad[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~
paint.cpp:38:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             for (int k = 0; k < kad[i+1].size(); k++) {
      |                             ~~^~~~~~~~~~~~~~~~~

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