Submission #307919

#	Time	Username	Problem	Language	Result	Execution time	Memory
307919		tjdgus4384	Painting Walls (APIO20_paint)	C++14	100 / 100	427 ms	15196 KiB

paint

#include<bits/stdc++.h>
using namespace std;

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int> > B){
    vector<int> v[100001];
    int prev, cnt[50001] = {0,}, ncnt[50001];
    int chk[50001] = {0,}, nchk[50001], ans = 0;
    bool istrue[100001];
    for(int i = 0;i < M;i++){
        for(int j = 0;j < A[i];j++){
            v[B[i][j]].push_back(i);
        }
    }
    for(int i = 0;i < N;i++){
        istrue[i] = false;
        for(int j = 0;j < v[C[i]].size();j++){
            if(v[C[i]][j] == 0) prev = M-1;
            else prev = v[C[i]][j]-1;
            if(cnt[prev] == i - 1){
                nchk[v[C[i]][j]] = chk[prev]+1;
                ncnt[v[C[i]][j]] = i;
            }
            else{
                nchk[v[C[i]][j]] = 0;
                ncnt[v[C[i]][j]] = i;
            }
        }
        for(int j = 0;j < v[C[i]].size();j++){
            cnt[v[C[i]][j]] = ncnt[v[C[i]][j]];
            chk[v[C[i]][j]] = nchk[v[C[i]][j]];
            if(chk[v[C[i]][j]] >= M-1) istrue[i] = true;
        }
    }
    for(int i = M-1, j = M-1;i < N;i++){
        if(j >= N) j=N-1;
        while(j >= i){
            if(istrue[j]) {ans++;i = j;j+=M;break;}
            j--;
        }
        if(j < i) 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:25: 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 < v[C[i]].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~
paint.cpp:28:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int j = 0;j < v[C[i]].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~

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