Submission #939109

#	Time	Username	Problem	Language	Result	Execution time	Memory
939109		sleepntsheep	Job Scheduling (CEOI12_jobs)	C11	100 / 100	186 ms	31604 KiB

jobs

#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);
      |                           ^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100