제출 #939088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
939088		vjudge1	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	1102 ms	65536 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 1<<20

int alc,A[N],B[N],L[N],R[N],S[N];
int tt(int x)
{
    int p=++alc;
    A[p]=x;
    B[p]=rand_();
    L[p]=R[p]=0;
    S[p]=1;
    return p;
}

void ts(int v,int*l,int*r,int k)
{
    if(!v){*l=*r=0;return;}

    if(S[L[v]]+1<=k)
    {
        ts(R[v],R+v,r,k-S[L[v]]-1);
        *l=v;
    }
    else
    {
        ts(L[v],l,L+v,k);
        *r=v;
    }
    S[v]=S[L[v]]+S[R[v]]+1;
}

void tm(int*v,int l,int r)
{
    if(!l||!r){*v=l^r;return;}
    if(B[l]>B[r])
    {
        tm(L+r,l,L[r]);
        *v=r;
    }
    else
    {
        tm(R+l,R[l],r);
        *v=l;
    }
    S[*v]=S[L[*v]]+S[R[*v]]+1;
}

int to(int v,int k)
{
    if(!v)return 0;
    if(A[v]<=k)return 1+S[L[v]]+to(R[v],k);
    return to(L[v],k);
}

int n,m,d,a[1<<20],ao,b[1<<20],*eh[N],eo[N];
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;
}

void tp(int v)
{
    if(!v)return;
    tp(L[v]);
    printf(" %d ", A[v]);
    tp(R[v]);
}

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-d;++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,ok=1,t=alc=0;
        for (int i=1;i<=o;++i)tm(&t,t,tt(1));

        for(int i=1;ok&&i<=n-d;++i)
        {
            //if(o==2) { printf(" Day %d (%d)\n",i,eo[i]); }
            for(int j=0;ok&&j<eo[i];++j)
            {
                int ded=i+d;
                int t1,t2,t3,t4,cc=to(t,ded);
                if(cc==0){ok=0;break;}
                ts(t,&t3,&t4,cc);
                ts(t3,&t2,&t1,cc-1);
                if(A[t1]<i)A[t1]=i;
                ++A[t1];
                tm(&t3,t2,t4);
                int dd=to(t3,A[t1]);
                ts(t3,&t2,&t4,dd);
                tm(&t3,t2,t1);
                tm(&t,t3,t4);

                //if(o==2) { tp(t); puts(""); }
            }
        }

        if(ok) r=o-1;
        else l=o+1;
    }

    alc=0;
    int t=0;
    for(int i=1;i<=r+1;++i)tm(&t,t,tt(1));

    for(int i=1;i<=n-d;++i)
    {
        for(int j=0;j<eo[i];++j)
        {
            int ded=d+i,t1,t2,t3,t4,cc=to(t,ded);
            ts(t,&t3,&t4,cc);
            ts(t3,&t2,&t1,cc-1);
            if(A[t1]<i)A[t1]=i;
            //printf(" : %d AT %d\n",eh[i][j],A[t1]);
            append(100001+(A[t1]++),eh[i][j]);
            tm(&t3,t2,t4);
            int dd=to(t3,A[t1]);
            ts(t3,&t2,&t4,dd);
            tm(&t3,t2,t1);
            tm(&t,t3,t4);
        }
    }

    printf("%d\n",r+1);
    for(int i=1;i<=n;++i)
    {
        //printf("%d",eo[i+100001]);
        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
*/

컴파일 시 표준 에러 (stderr) 메시지

jobs.cpp: In function 'int main()':
jobs.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d%d%d",&n,&d,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
jobs.cpp:78:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     for (int i=1;i<=m;++i)scanf("%d",b+i),append(b[i],i);
      |                           ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 100