Submission #980437

#TimeUsernameProblemLanguageResultExecution timeMemory
980437sleepntsheepPainting Walls (APIO20_paint)C++11
40 / 100
1593 ms112488 KiB
#pragma GCC optimize("O2,unroll-loops") #include "paint.h" #include<stdio.h> #include<map> #include<time.h> #include<stdlib.h> #define assert(x) if (!(x)) *(volatile int*)0=0; 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[MM],eo[MM],*fh[KK],fo[KK],freq[NN],*ll,lo,dp[NN]; int get(int cc, int pp) { if(cc<0)return 0; int lb=-1,ub=eo[cc]; while(ub-lb>1) { int mid=lb+(ub-lb)/2; if(eh[cc][mid]<=pp) lb=mid; else ub=mid; } if(lb==-1||eh[cc][lb]!=pp)return 0; return fh[cc][lb]; } int minimumInstructions( int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) { srand(time(0)); int counter=0; for(int i=0;i<M;++i) for(int j=0;j<A[i];++j) assert(++counter<4000000); for(int i=0;i<N;++i)push(fh,fo,C[i],i); for(int i=0;i<M;++i) { for(int j=0;j<A[i];++j) for(int k=0;k<fo[B[i][j]];++k) if(!freq[fh[B[i][j]][k]]++) { push(eh,eo,i,fh[B[i][j]][k]); // upperbound on #push is NOT O(400000) :( } sort(eh[i],0,eo[i]); for(int k=0;k<eo[i];++k) freq[eh[i][k]]=0; } for(int i=0;i<N;++i)fo[i]=0,free(fh[i]),fh[i]=0; for(int i=0;i<M;++i) for(int j=0;j<eo[i];++j) push(fh,fo,i,1+get(i-1,eh[i][j]-1)); for(int i=0;i<M;++i) for(int j=0;j<eo[i];++j) fh[i][j]=min(M,max(fh[i][j],1+get((M+i-1)%M,eh[i][j]-1))); for(int i=0;i<M;++i) for(int j=0;j<eo[i];++j) // can paint [eh[i][j] - M + 1, eh[i][j]] if(fh[i][j]==M) push_(&ll,&lo,eh[i][j]-M+1); 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) { int ii=rr[i][j]; if(!--in[ii])in.erase(ii); } 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) eo[i]=fo[i]=0,free(eh[i]),free(fh[i]),eh[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:39:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   39 |     else if(!(o&o-1))eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
      |                 ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...