Submission #980466

#	Time	Username	Problem	Language	Result	Execution time	Memory
980466		sleepntsheep	Painting Walls (APIO20_paint)	C++11	63 / 100	1563 ms	249108 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;}
void sort(int*a,int l,int r)
{
    while(l<r)
    {
        int i=l,j=l,k=r,t,p=a[l+rand()%(r-l)];
        while(j<k)
        {
            int c=a[j]-p;
            if(c<0)t=a[i],a[i]=a[j],a[j]=t,++i,++j;
            else if(!c)++j;
            else t=a[--k],a[k]=a[j],a[j]=t;
        }
        sort(a,l,i);
        l=k;
    }
}

#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); }

int*eh[2],eo[2],*fh[KK],fo[KK],*ll,lo,dp[NN],*gh[2],go[2];
int 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]];
}

int counter2=0;
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)
    {
        free(eh[i&1]);eo[i&1]=0;eh[i&1]=0;
        free(gh[i&1]);go[i&1]=0;gh[i&1]=0;

        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)
                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;
    }

    sort(ll,0,lo);

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

    {
        std::map<int,int>in={{1000000000,1}};
        static int *rr[NN],ro[NN];
        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;
        }

        for(int i=0;i<N;++i)
            free(rr[i]),rr[i]=0;
    }

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

    eo[0]=eo[1]=go[0]=go[1]=0;
    eh[0]=eh[1]=gh[0]=gh[1]=0;

    for(int i=0;i<M;++i)
        fo[i]=0,free(fh[i]),fh[i]=0;
    lo=0; free(ll),ll=0;

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

Compilation message (stderr)

paint.cpp: In function 'void push(int**, int*, int, int)':
paint.cpp:40:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   40 |     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:82:27: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   82 |         for(int j=0;j<eo[i&1^1];++j)
      |                          ~^~
paint.cpp:83:20: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   83 |             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: 0 / 37