Submission #469853

#	Time	Username	Problem	Language	Result	Execution time	Memory
469853		goatgm03	Job Scheduling (CEOI12_jobs)	C++17	95 / 100	619 ms	33416 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define v vector
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define f first
#define s second
const int mx=1e6+5;
int n,d,m;
pair<bool,v<v<int> > > possible(const v<pii>t,int mid){
    int cur=0;
    v<v<int> >res(n);
    for(int day=1;day<=n;day++){
        for(int j=0;j<mid;j++){
            if(t[cur].f>day){
                break;
            }
            if(t[cur].f+d<day)
                return {false,res};
            else if(t[cur].f+d>=day){
                res[day-1].pb(t[cur].s);
                cur++;
            }
            if(cur==m){
                return {true,res};
            }
        }
    }
    return {false,res};
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    // clock_t startTime = clock();
    cin>>n>>d>>m;
    v<v<int> >ans;
    v<pii>t(m);
    for(int i=0;i<m;i++){
        cin>>t[i].f;
        t[i].s=i+1;
    }
    sort(t.begin(),t.begin()+m);
    int lo=1,hi=m,sol=m;
    while(lo<hi){
        int mid=(hi+lo)/2;
        pair<bool,v<v<int> > >c=possible(t,mid);
        if(!c.f){
            lo=mid+1;
        }
        else{
            ans=c.s;
            hi=mid;
        }
    }
    cout<<lo<<endl;
    /*while(lo<hi){
        v<v<int> >result(n+1);
        int mid=(hi+lo)/2;
        int day=1,cur=0;
        bool too_few_machines=false;
        for(int day=1;day<=n;day++){
            for(int j=0;j<mid;j++){
                if(t[cur].f>day){
                    break;
                }
                if(t[cur].f+d>=day){
                    result[day].pb(t[cur].s);
                    cur++;
                }
                else if(t[cur].f+d<day){
                    too_few_machines=true;
                    break;
                }
                if(cur==m)
                    break;
                else if(t[cur].f+d>=day&&t[cur].f<=day){
                    cur++;
                }
            }
        }
        if(!too_few_machines&&cur==m){
            hi=mid;
            sol=min(sol,mid);
            ans=result;    
            // sol=min(sol,mid);
        }
        else{
            lo=mid+1;
        }
        cout<<mid<<endl;
    }
    int day=1,cur=0;
    v<v<int> >each_day(n+1);
    cout<<sol<<endl;
    for(int day=1;day<=n;day++){
        for(int j=0;j<sol;j++){        
            if(t[cur].f>day){
                break;
            }
            if(t[cur].f+d>=day){
                each_day[day].pb(t[cur].s);
                cur++;
            }
        }
    }*/
    for(int i=0;i<n;i++){
        if((int)ans[i].size()==0){
            cout<<"0\n";
            continue;
        }
        for(int j:ans[i])
            cout<<j<<' ';
        cout<<"0\n";
    }
    // cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< endl;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:44:19: warning: unused variable 'sol' [-Wunused-variable]
   44 |     int lo=1,hi=m,sol=m;
      |                   ^~~

• Subtask 1: 95 / 100