Submission #567745

#	Time	Username	Problem	Language	Result	Execution time	Memory
567745		Bill_00	Painting Walls (APIO20_paint)	C++14	100 / 100	514 ms	13268 KiB

paint

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "paint.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;

vector<vector<int> > V; 
vector<int> X, Y, Z;
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int> > B){
    V.resize(K);
    X.resize(M);
    Y.resize(M);
    Z.resize(N);
    for(int i = 0; i < M; i++){
        for(int j = 0; j < B[i].size(); j++){
            V[B[i][j]].push_back(i);
        }
    }
    for(int i = 0; i < N; i++){
        int mx = 0;
        for(int pos : V[C[i]]){
            Y[pos] = X[pos == 0 ? (M - 1) : (pos - 1)] + 1;
        }
        if(i){
            for(int pos : V[C[i - 1]]){
                X[pos] = 0;
            }
        }
        for(int pos : V[C[i]]){
            X[pos] = Y[pos];
            mx = max(mx, X[pos]);
            // cout << X[pos] << ' ';
        }
        if(mx >= M){
            Z[i] = 1;
        }
        // cout << Z[i] << ' ';
    }
    // cout << '\n';
    if(Z[M - 1] == 0) return -1;
    int last = M;
    int ans = 1;
    while(last < N){
        bool flag = 0;
        for(int i = min(N - 1, last + M - 1); i >= last; i--){
            if(Z[i] == 1){
                ans++;
                last = i + 1;
                flag = 1;
                break;
            }
        }
        if(flag == 0) return -1;
    }
    return ans;
}

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:16:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for(int j = 0; j < B[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~

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