Submission #763752

#	Time	Username	Problem	Language	Result	Execution time	Memory
763752		Petrix	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	281 ms	13968 KiB

jobs

#include <iostream>
#include <algorithm>
using namespace std;

struct vc{
    int a,ind;
}v[1000000];

bool cmp(vc a,vc b){
    if(a.a<b.a)
        return 1;
    else
        return 0;
}

int n,m;

bool verf(int mij,int d,int n,int m){
    int z,i,rasp,stg,j,poz;
    i=stg=1;poz=0;
    ///printf("%d \n",v[2].a);

    while(i<=n && stg && poz<m){///printf("a");
        for(j=0;j<mij&& poz<m;j++){
            //printf("%d ",poz);
            if(v[poz].a>i){//printf("| %d %d |",v[poz].a,i);
                break;
            }else if(v[poz].a+d<i && poz<m){
                //printf("{%d %d} ",v[poz].a+d,i);
                stg=0;
                break;
            }else{
                poz++;
            }
        }
        i++;
    }
    //printf("mij: %d | i (<=n) : %d | poz (==m) : %d | stg(==1) : %d\n",mij,i,poz,stg);
    if(i<=n && poz==m && stg==1)
        return 1;
    else
        return 0;
}

int main()
{
    int st,dr,mij,d,rasp,i,vf,j, stg,poz;
    cin>>n>>d>>m;
    for(i=0;i<m;i++){
        cin>>v[i].a;
        v[i].ind=i+1;
    }
    sort(v,v+m,cmp);

    st=1;dr=m/d+1;rasp=mij=0;
    while(st<dr){
        mij=(st+dr)/2;
        vf=verf(mij,d,n,m);
        if(vf==1){
            rasp=mij;
            dr=mij-1;
        }else{
            st=mij+1;
        }
    }
    cout<<rasp<<"\n";
    mij=rasp;
    i=stg=1;poz=0;
    while(i<=n && stg ){///printf("a");
        for(j=0;j<mij;j++){
            if(v[poz].a>i)
                break;
            else{
                printf("%d ",v[poz].ind);
                poz++;
            }

        }
        printf("0\n");
        i++;
    }

    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'bool verf(int, int, int, int)':
jobs.cpp:19:9: warning: unused variable 'z' [-Wunused-variable]
   19 |     int z,i,rasp,stg,j,poz;
      |         ^
jobs.cpp:19:13: warning: unused variable 'rasp' [-Wunused-variable]
   19 |     int z,i,rasp,stg,j,poz;
      |             ^~~~

• Subtask 1: 0 / 100