oj.uz

Submission #939107

# Submission time Handle Problem Language Result Execution time Memory
939107 2024-03-06T05:46:24 Z sleepntsheep Job Scheduling (CEOI12_jobs) C
0 / 100
 196 ms 64852 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 1<<20

int n,m,d,b[1<<20],*eh[N],eo[N],a[N],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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 40 ms 45332 KB Memory limit exceeded
2 Runtime error 40 ms 45188 KB Memory limit exceeded
3 Runtime error 40 ms 45156 KB Memory limit exceeded
4 Runtime error 40 ms 45148 KB Memory limit exceeded
5 Runtime error 43 ms 45140 KB Memory limit exceeded
6 Runtime error 40 ms 45136 KB Memory limit exceeded
7 Runtime error 40 ms 45140 KB Memory limit exceeded
8 Runtime error 41 ms 45148 KB Memory limit exceeded
9 Runtime error 43 ms 45652 KB Memory limit exceeded
10 Runtime error 55 ms 45700 KB Memory limit exceeded
11 Runtime error 41 ms 45392 KB Memory limit exceeded
12 Runtime error 59 ms 47608 KB Memory limit exceeded
13 Runtime error 75 ms 54864 KB Memory limit exceeded
14 Runtime error 103 ms 56136 KB Memory limit exceeded
15 Runtime error 106 ms 56916 KB Memory limit exceeded
16 Runtime error 137 ms 58592 KB Memory limit exceeded
17 Runtime error 182 ms 62804 KB Memory limit exceeded
18 Runtime error 196 ms 63316 KB Memory limit exceeded
19 Runtime error 178 ms 64852 KB Memory limit exceeded
20 Runtime error 156 ms 62768 KB Memory limit exceeded