Submission #547495

#	Time	Username	Problem	Language	Result	Execution time	Memory
547495		Deepesson	Painting Walls (APIO20_paint)	C++17	40 / 100	1609 ms	220704 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define MAX 105000
typedef std::pair<int,int> pii;
std::map<pii,pii> pai;
std::map<pii,int> size;
int mod(int p,int M){
    p%=M;
    if(p<0)p+=M;
    return p;
}

void check(pii k){
    if(pai.find(k)==pai.end()){
        pai[k]=k;
        size[k]=1;
    }
}

pii find(pii x){
    assert(x.second<700);
    check(x);
    auto&ref = pai[x];
    if(ref==x)
        return x;
    return ref=find(ref);
}

void Union(pii a,pii b){
    a=find(a);
    b=find(b);
    if(a!=b){
        auto& ref1 = size[a],ref2=size[b];
        if(ref1>ref2)std::swap(a,b);
        pai[a]=b;
        ref1+=ref2;
    }
}
bool pode[MAX];
std::vector<int> curte[MAX];
int get_num(int pos,int val){
    int l=0,r=curte[pos].size()-1;
    if(r<l)return -1;
    int obj = val;
    while(l<r){
        int m = (l+r+1)/2;
        if(curte[pos][m]>obj){
            r=m-1;
        }else l=m;
    }
    if(l<0)return -1;
  ///  std::cout<<pos<<" "<<l<<"\n";
    if(curte[pos][l]==val)return l;
    return -1;
}
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-1;++i){
        int cor1 = C[i],cor2 = C[i+1];
        for(int j=0;j!=curte[cor1].size();++j){
            auto x=curte[cor1][j];
            int tipo = x,prox = mod(x+1,M);
            bool ok=false;
           /// std::cout<<"Tentando "<<j<<" "<<i<<"\n";
            int ans;
            {
                int l=0,r=curte[cor2].size()-1;
                if(r<l)break;
                int obj = prox;
                while(l<r){
                    int m = (l+r+1)/2;
                    if(curte[cor2][m]>obj){
                        r=m-1;
                    }else l=m;
                }
                if(curte[cor2][l]==obj)ok=true;
                ans=l;
            }
         ///   std::cout<<"Tentou\n";
            if(ok)
            {
                Union({i,j},{i+1,ans});
              ///  std::cout<<"Liga "<<i<<" "<<j<<" com: "<<i+1<<" "<<ans<<"\n";

            }
        }
    }
    for(int i=0;i!=N;++i){
        int fim = i+M-1;
        if(fim>=N)break;
       /// std::cout<<"Checa "<<i<<"\n";
        for(int j=0;j!=curte[C[i]].size();++j){
            auto x=curte[C[i]][j];
            int ultimo_pintor = mod(x-1,M);
            int ind1 = j,ind2 = get_num(C[fim],ultimo_pintor);
           /// std::cout<<"Ind "<<ind2<<"\n";
            if(ind2==-1)continue;
            pii alpha = find({i,ind1});
            pii beta = find({fim,ind2});
           /// std::cout<<"Busca "<<i<<" "<<ind1<<" "<<fim<<" "<<ind2<<"\n";
            ///std::cout<<alpha.first<<" "<<alpha.second<<" "<<beta.first<<" "<<beta.second<<"!\n";
            if(alpha==beta){
              ///  std::cout<<"Conexao "<<i<<" "<<fim<<"\n";
                pode[i]=true;
                break;
            }
        }
    }

    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:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j=0;j!=curte[cor1].size();++j){
      |                     ~^~~~~~~~~~~~~~~~~~~~
paint.cpp:66:17: warning: unused variable 'tipo' [-Wunused-variable]
   66 |             int tipo = x,prox = mod(x+1,M);
      |                 ^~~~
paint.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int j=0;j!=curte[C[i]].size();++j){
      |                     ~^~~~~~~~~~~~~~~~~~~~
paint.cpp:116:9: warning: unused variable 'min' [-Wunused-variable]
  116 |     int min = 1e9;
      |         ^~~

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