Submission #1347008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1347008		DanielPr8	Painting Walls (APIO20_paint)	C++20	40 / 100	833 ms	154488 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
using ll = int;
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){
    ll m2=m;
    vll tp;
    while(m2>0){
        tp.pb(m2%2);
        m2/=2;
    }
    reverse(all(tp));
    vvl col(k);
    for(ll i = 0; i < n; ++i)col[c[i]].pb(i);
    vvl pa(n), pa2(n), pa3(n);
    for(ll i = 0; i < m; ++i){
        for(ll j:b[i]){
            for(ll h: col[j])pa[h].pb(i);
        }
    }
    for(ll i = 0; i < n; ++i)sort(all(pa[i]));
    pa3=pa;
    ll cur=1;
    for(ll f = 1; f < tp.size(); ++f){
        for(ll i = 0; i+cur*2 <= n; ++i){
            pa2[i] = merg(pa[i], pa[i+cur], cur, m);
        }
        swap(pa,pa2);
        cur*=2;
        if(tp[f]==1){
            for(ll i = 0; i+cur+1 <= n; ++i){
                pa2[i] = merg(pa[i], pa3[i+cur], cur, m);
            }
            cur++;
        }
    }
    multiset<ll> pq;
    pq.insert(0);
    vvl er(n);
    er[0]={0};
    for(ll i = 0; i <= n-m; ++i){
        if(i==n-m){
            if(pa[i].empty())return -1;
            ll mn = *(pq.begin());
            return mn+1;
        }

        if(!pa[i].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));
        }
    }

}

Compilation message (stderr)

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

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