Submission #1153203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153203		Math4Life2020	Painting Walls (APIO20_paint)	C++20	100 / 100	1018 ms	292296 KiB

paint

#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;

const ll INF = 1e8;

const ll Nm = (1<<17); const ll E = 17;
vector<ll> stdp;

void upd(ll p, ll v) {
    if (p==0) {
        return;
    }
    stdp[p]=min(stdp[p],v);
    upd(p/2,v);
}

inline ll v2(ll x) {
    return __builtin_ctz(x);
}

ll gmin(ll a, ll b) {
    if (a>b) {
        return INF;
    }
    ll va = v2(a); ll vb = v2(b+1);
    if (va<vb) {
        return min(stdp[(a>>va)+(1<<(E-va))],gmin(a+(1<<va),b));
    } else {
        return min(stdp[(b>>vb)+(1<<(E-vb))],gmin(a,b-(1<<vb)));
    }
}

ll minimumInstructions(ll N, ll M, ll K, vector<ll> C, vector<ll> A, vector<vector<ll>> B) {
    stdp.clear();
    for (ll i=0;i<(2*Nm);i++) {
        stdp.push_back(INF);
    }
    vector<ll> indC[K];
    for (ll i=0;i<M;i++) {
        for (ll j=0;j<A[i];j++) {
            indC[B[i][j]].push_back(i);
        }
    }
    vector<ll> trm[M];
    for (ll x=0;x<N;x++) {
        for (ll y: indC[C[x]]) {
            //cout << "C[x]="<<C[x]<<"; ";
            //cout << "x,y: "<<x<<","<<y<<"; ";
            //cout << "trm: "<<((y+M-(x%M))%M)<<"\n";
            trm[(y+M-(x%M))%M].push_back(x);
        }
    }
    vector<bool> isV(N-M+1,false);
    for (ll m=0;m<M;m++) {
        if (trm[m].size()<M) {
            continue;
        }
        sort(trm[m].begin(),trm[m].end());
        for (ll xc=0;xc<=(ll)(trm[m].size()-M);xc++) {
            if ((trm[m][xc+M-1]-trm[m][xc])==(M-1)) {
                isV[trm[m][xc]]=1;
                //cout << "isV = 1 at "<<trm[m][xc]<<"\n";
            }
        }
    }
    if (!isV[0]) {
        return -1;
    }
    upd(Nm,1);
    for (ll i=1;i<=(N-M);i++) {
        if (isV[i]) {
            stdp[i+Nm]=min(INF,gmin(max(i-M,0),i-1)+1);
            //cout << "stdp at i="<<i<<" is "<<stdp[i]<<"\n";
            if (stdp[i+Nm]<INF) {
                upd(i+Nm,stdp[i+Nm]);
            }
        }
    }
    if (stdp[N-M+Nm]>=INF) {
        return -1;
    }
    return stdp[N-M+Nm];
}

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