Submission #939109

#TimeUsernameProblemLanguageResultExecution timeMemory
939109sleepntsheepJob Scheduling (CEOI12_jobs)C11
100 / 100
186 ms31604 KiB
#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)

jobs.c: In function 'main':
jobs.c:32:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%d%d%d",&n,&d,&m);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~
jobs.c:34:27: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     for (int i=1;i<=m;++i)scanf("%d",b+i),append(b[i],i);
      |                           ^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...