Submission #547485

#	Time	Username	Problem	Language	Result	Execution time	Memory
547485		Deepesson	Painting Walls (APIO20_paint)	C++17	40 / 100	1603 ms	231528 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){
    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];
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    std::vector<int> curte[K];
    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(auto&x:curte[cor1]){
            int tipo = x,prox = mod(x+1,M);
            bool ok=false;
            {
                int l=0,r=B[prox].size()-1;
                int obj = cor2;
                while(l<r){
                    int m = (l+r+1)/2;
                    if(B[prox][m]>obj){
                        r=m-1;
                    }else l=m;
                }
                if(B[prox][l]==cor2)ok=true;
            }
            if(ok)
            {
               /// std::cout<<"Liga "<<i<<" "<<tipo<<" com: "<<i+1<<" "<<prox<<"\n";
                Union({i,tipo},{i+1,prox});
            }
        }
    }
    for(int i=0;i!=N;++i){
        int fim = i+M-1;
        if(fim>=N)break;
        for(auto&x:curte[C[i]]){
            int ultimo_pintor = mod(x-1,M);
            pii alpha = find({i,x});
            pii beta = find({fim,ultimo_pintor});
           /// std::cout<<"Busca "<<i<<" "<<x<<" "<<fim<<" "<<ultimo_pintor<<"\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:88:9: warning: unused variable 'min' [-Wunused-variable]
   88 |     int min = 1e9;
      |         ^~~

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