Submission #963991

#	Time	Username	Problem	Language	Result	Execution time	Memory
963991		efedmrlr	Painting Walls (APIO20_paint)	C++17	100 / 100	498 ms	15124 KiB

paint

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

using namespace std;


#define lli long long int

#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;

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

    vector<vector<int> > col(K, vector<int>());
    vector<array<int,2> > dp, dpn;
    vector<int> mx(N, 0);

    swap(A, C);
    // for(auto c : A) {
    //     cout << c << " ";
    // }
    // cout << endl;
    for(int i = 0; i < M; i++) {
        for(auto c : B[i]) {
            col[c].pb(i);
        }
    }
    for(int i = 0; i < N; i++) {
        int itr = 0;
        for(auto c : col[A[i]]) {
            int val = c - 1;
            if(c == 0) {
                val = M - 1;
                if(dp.size() > 0 && dp.back()[0] == val) {
                    mx[i] = max(mx[i], dp.back()[1] + 1);
                    dpn.pb({c, dp.back()[1] + 1});
                }
                else {
                    mx[i] = max(mx[i], 1);
                    dpn.pb({c, 1});
                }
                continue;
            }
            while(itr < dp.size() && dp[itr][0] < val) {
                itr++;
            }
            if(itr >= dp.size() || dp[itr][0] != val) {
                mx[i] = max(mx[i], 1);
                dpn.pb({c, 1});
            }
            else {
                mx[i] = max(mx[i], dp[itr][1] + 1);
                dpn.pb({c, dp[itr][1] + 1});
            }
        }
        swap(dp, dpn);
        dpn.clear();
    }
    vector<int> vals;
    for(int i = 0; i < N; i++) {
        if(mx[i] >= M) {
            vals.pb(i);
        }
    }
    // for(auto c : vals) {
    //     cout << c << " ";
    // }
    // cout << endl;
    int bor = M - 1;
    int ans = 0;
    while(1) {
        auto itr = upper_bound(all(vals), bor) - vals.begin();
        itr--;
        if(itr < 0 || vals[itr] <= bor - M) {
            return -1;
        }
        ans++;
        if(vals[itr] == N - 1) break;
        bor = vals[itr] + M;
    }
    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:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             while(itr < dp.size() && dp[itr][0] < val) {
      |                   ~~~~^~~~~~~~~~~
paint.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             if(itr >= dp.size() || dp[itr][0] != val) {
      |                ~~~~^~~~~~~~~~~~

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