#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<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
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 time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
