Submission #892765

#	Time	Username	Problem	Language	Result	Execution time	Memory
892765		betterdanjoe	Painting Walls (APIO20_paint)	C++17	100 / 100	595 ms	253008 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];
    vector<int> len[N];
    for(int i = 0; i < M; i++){
        for(int j : B[i]){
            pos[j].pb(i);
        }
    }
    for(int i = 0; i < N; i++){
        if(pos[C[i]].size() == 0) return -1;
        len[i].resize(pos[C[i]].size(), 0);
    }
    for(int i = N - 1; i >= 1; i--){
        int ind = 0;
        for(int j = 0; j < pos[C[i]].size(); j++){
            while(ind < pos[C[i - 1]].size() && pos[C[i - 1]][ind] < pos[C[i]][j] - 1) ind++;
            if(ind < pos[C[i - 1]].size() && pos[C[i - 1]][ind] == pos[C[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 < pos[C[i]].size(); j++){
            if(len[i][j] == M - 1){
                check[i] = true;
                break;
            }
            if(len[i][j] == M - 1 - pos[C[i]][j] && pos[C[i + len[i][j] + 1]][0] == 0 && len[i + len[i][j] + 1][0] >= pos[C[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:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int j = 0; j < pos[C[i]].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~
paint.cpp:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             while(ind < pos[C[i - 1]].size() && pos[C[i - 1]][ind] < pos[C[i]][j] - 1) ind++;
      |                   ~~~~^~~~~~~~~~~~~~~~~~~~~~
paint.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             if(ind < pos[C[i - 1]].size() && pos[C[i - 1]][ind] == pos[C[i]][j] - 1){
      |                ~~~~^~~~~~~~~~~~~~~~~~~~~~
paint.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int j = 0; j < pos[C[i]].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~

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