제출 #1346994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1346994		DanielPr8	Painting Walls (APIO20_paint)	C++20	40 / 100	495 ms	589824 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
using vi = vector<int>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()

vll merg(vll& x, vll& y, ll t, ll m){
    if(x.empty() || y.empty())return {};
    ll i=0, j = lower_bound(all(y),t)-y.begin(), o=0;
    j%=y.size();
    ll p = y[j];
    vll ans;
    while(i<x.size() && (y[j]!=p || o==0)){
        if(x[i]==(y[j]+m-t)%m){
            ans.pb(x[i]);
            i++;
            if(y[j]==p)o=1;
            j=(j+1)%y.size();
        }
        else if(x[i]<(y[j]+m-t)%m){
            i++;
        }
        else{
            if(y[j]==p)o=1;
            j=(j+1)%y.size();
        }
    }
    return ans;
}

int minimumInstructions(int n, int m, int k, vi c, vi a, vector<vi> b){
    vvl col(k);
    for(ll i = 0; i < n; ++i)col[c[i]].pb(i);
    vector<vvl> pa(20, vvl(n));
    for(ll i = 0; i < m; ++i){
        for(ll j:b[i]){
            for(ll h: col[j])pa[0][h].pb(i);
        }
    }
    for(ll i = 0; i < n; ++i)sort(all(pa[0][i]));
    for(ll f = 1; f < 20; ++f){
        for(ll i = 0; i+(1<<f) <= n; ++i){
            pa[f][i] = merg(pa[f-1][i], pa[f-1][i+(1<<(f-1))], (1<<(f-1)), m);
        }
    }
    multiset<ll> pq;
    pq.insert(0);
    vvl er(n);
    er[0]={0};
    for(ll i = 0; i <= n-m; ++i){
        vll op;ll o = 0;
        for(ll f = 19; f >= 0; --f){
            if(m-o>=(1<<f)){
                if(o==0)op = pa[f][i];
                else op = merg(op, pa[f][i+o], o, m);
                o+=(1<<f);
            }
        }
        if(i==n-m){
            if(op.empty())return -1;
            ll mn = *(pq.begin());
            return mn+1;
        }

        if(!op.empty()){
            if(pq.empty())return -1;
            ll mn = *(pq.begin());
            pq.insert(mn+1);
            er[i+m].pb(mn+1);
        }

        for(ll j: er[i]){
            pq.erase(pq.find(j));
        }
    }

}

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'int minimumInstructions(int, int, int, vi, vi, std::vector<std::vector<int> >)':
paint.cpp:86:1: warning: control reaches end of non-void function [-Wreturn-type]
   86 | }
      | ^

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