This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "paint.h"
#include<stdio.h>
#include<set>
#include<time.h>
#include<stdlib.h>
int max(int i,int j){return i>j?i:j;}
int min(int i,int j){return i<j?i:j;}
int(*compar)(int,int);
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=compar(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;
}
}
int ij(int i,int j){return 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); }
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));
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 O(400000)
compar=ij;
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]);
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::multiset<int>in={1000000000};
static int *rr[NN],ro[NN];
for(int i=0;i<N;++i)
ro[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.insert(before+1);
if(i+M<N)
push(rr,ro,i+M,before+1);
++j;
}
for(int j=0;j<ro[i];++j)
in.erase(in.find(rr[i][j]));
dp[i]=*in.begin();
}
for(int i=0;i<N;++i)
free(rr[i]);
}
for(int i=0;i<M;++i)
eo[i]=fo[i]=0,free(eh[i]),free(fh[i]);
lo=0; free(ll);
return dp[N-1] >= 1e9 ? -1 : dp[N-1];
}
Compilation message (stderr)
paint.cpp: In function 'void push(int**, int*, int, int)':
paint.cpp:46:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
46 | else if(!(o&o-1))eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |