Submission #892760

#	Time	Username	Problem	Language	Result	Execution time	Memory
892760		betterdanjoe	Painting Walls (APIO20_paint)	C++17	12 / 100	56 ms	23600 KiB

paint

#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#endif
#include <bits/stdc++.h>
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;

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--){
        int ind = 0;
        for(int j = 0; j < val[i].size(); j++){
            while(ind < val[i - 1].size() && val[i - 1][ind] < val[i][j] - 1) ind++;
            if(ind < val[i - 1].size() && val[i - 1][ind] == val[i][j] - 1){
                len[i - 1][ind] = 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:39:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int j = 0; j < val[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
paint.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             while(ind < val[i - 1].size() && val[i - 1][ind] < val[i][j] - 1) ind++;
      |                   ~~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             if(ind < val[i - 1].size() && val[i - 1][ind] == val[i][j] - 1){
      |                ~~~~^~~~~~~~~~~~~~~~~~~
paint.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         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