Submission #892759

#	Time	Username	Problem	Language	Result	Execution time	Memory
892759		betterdanjoe	Painting Walls (APIO20_paint)	C++17	12 / 100	63 ms	24808 KiB

paint

#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

template<class K> using sset =  tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;

inline ll ceil0(ll a, ll b) {
    return a / b + ((a ^ b) > 0 && a % b);
}

void setIO() {
    ios_base::sync_with_stdio(0); cin.tie(0);
}

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
    vector<int> pos[K];
    for(int i = 0; i < N; i++){
        pos[C[i]].pb(i);
    }
    vector<int> val[N];
    vector<int> len[N];
    for(int i = 0; i < M; i++){
        for(int j : B[i]){
            for(int k : pos[j]){
                val[k].pb(i);
            }
        }
    }
    for(int i = 0; i < N; i++) len[i].resize(val[i].size(), 0);
    for(int i = N - 1; i >= 1; i--){
        for(int j = 0; j < val[i].size(); j++){
            int k = lower_bound(val[i - 1].begin(), val[i - 1].end(), val[i][j] - 1) - val[i - 1].begin();
            if(k == val[i - 1].size() || val[i - 1][k] != val[i][j] - 1) continue;
            len[i - 1][k] = len[i][j] + 1;
        }
    }
    bool check[N];
    memset(check, false, sizeof(check));
    for(int i = 0; i < N - M + 1; i++){
        for(int j = 0; j < val[i].size(); j++){
            if(len[i][j] == M - 1){
                check[i] = true;
                break;
            }
            if(len[i][j] == M - 1 - val[i][j] && val[i + len[i][j] + 1][0] == 0 && len[i + len[i][j] + 1][0] >= val[i][j] - 1){
                check[i] = true;
                break;
            }
        }
    }
    int cur = 0;
    int prv = 0;
    int ans = 0;
    while(cur < N){
        int nxt = -1;
        for(int i = prv; i <= cur; i++){
            if(check[i]) nxt = i + M;
        }
        if(nxt == -1) return -1;
        ans++;
        prv = cur + 1;
        cur = nxt;
    }
    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:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int j = 0; j < val[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
paint.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             if(k == val[i - 1].size() || val[i - 1][k] != val[i][j] - 1) continue;
      |                ~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int j = 0; j < val[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~

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