oj.uz

Submission #939109

# Submission time Handle Problem Language Result Execution time Memory
939109 2024-03-06T05:47:00 Z sleepntsheep Job Scheduling (CEOI12_jobs) C
100 / 100
 186 ms 31604 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12628 KB Output is correct
2 Correct 23 ms 12636 KB Output is correct
3 Correct 20 ms 12624 KB Output is correct
4 Correct 20 ms 12636 KB Output is correct
5 Correct 20 ms 12488 KB Output is correct
6 Correct 20 ms 12636 KB Output is correct
7 Correct 21 ms 12636 KB Output is correct
8 Correct 20 ms 12624 KB Output is correct
9 Correct 22 ms 12892 KB Output is correct
10 Correct 23 ms 12892 KB Output is correct
11 Correct 29 ms 12636 KB Output is correct
12 Correct 39 ms 14672 KB Output is correct
13 Correct 56 ms 22096 KB Output is correct
14 Correct 80 ms 23192 KB Output is correct
15 Correct 90 ms 24148 KB Output is correct
16 Correct 121 ms 25724 KB Output is correct
17 Correct 139 ms 29960 KB Output is correct
18 Correct 137 ms 30304 KB Output is correct
19 Correct 186 ms 31604 KB Output is correct
20 Correct 138 ms 29948 KB Output is correct