Submission #553048

#	Time	Username	Problem	Language	Result	Execution time	Memory
553048		Itamar	Painting Walls (APIO20_paint)	C++14	100 / 100	1453 ms	252636 KiB

paint

#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);
        }
    }
    for (int i = 0; i < K; i++)
        sort(com[i].begin(), com[i].end());
    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++) {
                int it = lower_bound(com[C[i + 1]].begin(), com[C[i + 1]].end(), (com[C[i]][j] + 1) % M) - com[C[i+1]].begin();
                if (it < com[C[i + 1]].size()) {
                    if (com[C[i + 1]][it] == (com[C[i]][j] + 1) % M) {
                        kad[i][j] = kad[i + 1][it] + 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:3: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    3 | #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:35:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   35 |         if (com[C[i]].empty())
      |         ^~
paint.cpp:37:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   37 |             for (int j = 0; j < kad[i].size(); j++) {
      |             ^~~
paint.cpp:37:31: 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:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |                 if (it < com[C[i + 1]].size()) {
      |                     ~~~^~~~~~~~~~~~~~~~~~~~~~

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