Submission #980536

#	Time	Username	Problem	Language	Result	Execution time	Memory
980536		sleepntsheep	Painting Walls (APIO20_paint)	C++11	100 / 100	652 ms	16468 KiB

paint

#pragma GCC optimize("O2,unroll-loops")

#include "paint.h"
#include<string.h>
#include<stdio.h>
#include<map>
#include<time.h>
#include<stdlib.h>

#define assert(x) if (!(x)) __builtin_trap()
int max(int i,int j){return i>j?i:j;}
int min(int i,int j){return i<j?i:j;}

#include <vector>

#define NN 100000
#define MM 50000
#define KK 100000

void push(int**eh,int*eo,int i,int j)
{
    int o=eo[i]++;
    if(!o)eh[i]=(int*)malloc(2*sizeof**eh);
    else if(!(o&o-1))eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
    eh[i][o]=j;
}
void push_(int**eh,int*eo,int j) { return push(eh,eo,0,j); }
void clear(int**eh,int*eo,int i){eo[i]=0;free(eh[i]);eh[i]=0;}

int*eh[2],eo[2],*fh[KK],fo[KK],*ll,lo,dp[NN],*gh[2],go[2],freq[NN],*rr[NN],ro[NN],at[MM];

int get(int cc, int pp)
{
    if(cc<0)return 0;
    if(at[pp]==-1)return 0;
    return gh[cc&1][at[pp]];
}

/* assume this function is only called once, it doesn't clear values */
int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
    memset(at,-1,sizeof at);

    srand(time(0));

    for(int i=0;i<M;++i)
        for(int j=0;j<A[i];++j)
            push(fh,fo,B[i][j],i);

    for(int i=0;i<N;++i)
    {
        clear(eh,eo,i&1);
        clear(gh,go,i&1);

        for(int j=0;j<fo[C[i]];++j)
            push(eh,eo,i&1,fh[C[i]][j]); /* N * sqrt(4e5) ? ? */

        for(int yy,j=0;j<eo[i&1];++j)
        {
            push(gh,go,i&1,yy=min(M,1+get(i-1,(M+eh[i&1][j]-1)%M)));
            if(yy==M&&!freq[i-M+1]++)
                push_(&ll,&lo,i-M+1);
        }

        for(int j=0;j<eo[i&1^1];++j)
            at[eh[i&1^1][j]]=-1;
        for(int j=0;j<eo[i&1];++j)
            at[eh[i&1][j]]=j;
    }

    for(int i=0;i<N;++i)freq[i]=0;
    for(int i=0;i<lo;++i)++freq[ll[i]];
    lo=0;
    for(int i=0;i<N;++i)while(freq[i]--)ll[lo++]=i;

    for(int i=0;i<N;++i) dp[i]=1e9;

    std::map<int,int>in={{1000000000,1}};
    for(int i=0;i<N;++i)
        ro[i]=0,rr[i]=0;

    for(int i=0,j=0;i<N;++i)
    {
        while(j<lo&&ll[j]<=i)
        {
            int before=ll[j]==0?0:dp[ll[j]-1];
            ++in[before+1];
            if(i+M<N)
                push(rr,ro,i+M,before+1);
            ++j;
        }
        for(int j=0;j<ro[i];++j)
            if(!--in[rr[i][j]])in.erase(rr[i][j]);
        dp[i]=in.begin()->first;
    }

    return dp[N-1] >= 1e9 ? -1 : dp[N-1];
}

Compilation message (stderr)

paint.cpp: In function 'void push(int**, int*, int, int)':
paint.cpp:24:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   24 |     else if(!(o&o-1))eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
      |                 ~^~
paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:66:27: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   66 |         for(int j=0;j<eo[i&1^1];++j)
      |                          ~^~
paint.cpp:67:20: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   67 |             at[eh[i&1^1][j]]=-1;
      |                   ~^~

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