Submission #469725

#	Time	Username	Problem	Language	Result	Execution time	Memory
469725		goatgm03	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	1098 ms	7244 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 main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    clock_t startTime = clock();
    int n,d,m;
    cin>>n>>d>>m;
    v<pii>t(m);
    for(int i=0;i<m;i++){
        cin>>t[i].f;
        t[i].s=i+1;
    }
    sort(all(t));
    int lo=1,hi=n,sol=n;
    while(lo<hi){
        int mid=(hi-lo)/2,cnt=0;
        int day=1,cur=0;
        for(int i=0;i<m;i++){
            if(t[i].f<=day&&day<=t[i].f+d){
                cnt++;
                cur++;
            }
            if(cur==mid){
                cur=0;
                day++;
            }
            // if(day>n||cnt==m)
                // break;
        }
        if(day<=n&&cnt>=m){
            hi=mid;
            sol=min(sol,mid);
        }
        else{
            lo=mid+1;
        }
    }
    int day=1,cur=0;
    v<v<int> >each_day(n+1);
    for(int i=0;i<m;i++){
        if(t[i].f<=day&&day<=t[i].f+d){
            cur++;
            each_day[day].pb(t[i].s);
        }
        if(cur==sol){
            cur=0;
            day++;
        }
    }
    cout<<sol<<endl;
    for(int i=1;i<=n;i++){
        if((int)each_day[i].size()==0){
            cout<<"0\n";
            continue;
        }
        for(int j:each_day[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:13:13: warning: unused variable 'startTime' [-Wunused-variable]
   13 |     clock_t startTime = clock();
      |             ^~~~~~~~~

• Subtask 1: 0 / 100