Submission #547692

#	Time	Username	Problem	Language	Result	Execution time	Memory
547692		Deepesson	Painting Walls (APIO20_paint)	C++17	100 / 100	569 ms	14940 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define MAX 100004
typedef std::pair<int,int> pii;
bool pode[MAX];
std::vector<int> curte[MAX];
int turno[MAX];
int seq[MAX];
int mod(int p,int M){
    p%=M;
    if(p<0)p+=M;
    return p;
}

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    for(int i=0;i!=M;++i){
        for(auto& x:B[i]){
            curte[x].push_back(i);
        }
    }
    for(int i=0;i!=N;++i){
        int cor1 = C[i];
        for(int j=0;j!=curte[cor1].size();++j){
            auto x = curte[cor1][j];
            int codigo = mod(i-x,M);
            if(turno[codigo]!=(i-1))seq[codigo]=0;
            ++seq[codigo];
            turno[codigo]=i;
            if(seq[codigo]>=M){
                pode[i-M+1]=true;
            }
        }
    }
    std::priority_queue<pii,std::vector<pii>,std::greater<pii>> queue;

    int min = 1e9;
    int last=0;

    for(int i=0;i!=N+1;++i){
        int ans=1e9;
        if(i){
            while(queue.size()){
                auto __ = queue.top();

                ///Invalido
                if(__.second<i-M){
                    queue.pop();
                    continue;
                }

                ans=__.first;
                break;

            }
        }else ans=0;

        if(pode[i])
        queue.push({ans+1,i});

     ///   std::cout<<"Custo "<<ans<<" ("<<i<<")\n";
        last=ans;
    }
    if(last>=1e9)return -1;
    ///Sucesso
    return last;
}

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:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int j=0;j!=curte[cor1].size();++j){
      |                     ~^~~~~~~~~~~~~~~~~~~~
paint.cpp:36:9: warning: unused variable 'min' [-Wunused-variable]
   36 |     int min = 1e9;
      |         ^~~

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