# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
939109 | sleepntsheep | Job Scheduling (CEOI12_jobs) | C11 | 186 ms | 31604 KiB |
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<stdio.h>
#include<stdlib.h>
int hi(int a,int b){return a>b?a:b;}
unsigned X=12345;int rand_(){return(X*=3)>>1;}
#define N 200005
int n,m,d,b[1<<20],*eh[N],eo[N],a[1<<20],ao;
void append(int i,int j)
{
int o=eo[i]++;
if(o>=2&&(o&(o-1))==0)eh[i]=(int*)realloc(eh[i],2*o*sizeof**eh);
eh[i][o]=j;
}
int ok(int o)
{
int p=0;
for(int i=1;i<=n;++i)
{
int cnt = 0;
while(p<m&&b[a[p]]<=i&&cnt+1<=o)
{
if(i>b[a[p]]+d)return 0;
++cnt;++p;
}
}
return p==m;
}
int main()
{
scanf("%d%d%d",&n,&d,&m);
for (int i=1;i<N;++i)eh[i]=(int*)malloc(2*sizeof**eh);
for (int i=1;i<=m;++i)scanf("%d",b+i),append(b[i],i);
for(int i=1;i<=n;++i)for(int j=0;j<eo[i];++j)a[ao++]=eh[i][j];
int l=1,r=m;
while(l<=r)
{
int o=(l+r)>>1;
if(ok(o)) r=o-1;
else l=o+1;
}
int p=0;
for(int i=1;i<=n;++i)
{
int cnt=0;
while(p<m&&b[a[p]]<=i&&cnt<=r+1)
{
append(100001+i,a[p]);
++cnt;++p;
}
}
printf("%d\n",r+1);
for(int i=1;i<=n;++i)
{
for (int j = 0; j < eo[i+100001];++j)printf("%d ",eh[i+100001][j]);
puts("0");
}
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |