Submission #392779

#	Time	Username	Problem	Language	Result	Execution time	Memory
392779		nicolaalexandra	Job Scheduling (CEOI12_jobs)	C++14	65 / 100	1094 ms	41060 KiB

jobs

#include <bits/stdc++.h>
#define DIM 1000010
using namespace std;

priority_queue <int,vector<int>,greater<int> > h;
pair <int,int> v[DIM];
vector <int> ans[DIM];
int n,d,m,i;

int verif (int val){
    while (!h.empty())
        h.pop();
    for (int i=1;i<=m;i++)
        ans[i].clear();

    for (int i=1;i<=val;i++)
        h.push(1);

    for (int i=1;i<=n;i++){
        int day = h.top();
        h.pop();
        if (day > v[i].first + d)
            return 0;

        ans[max(day,v[i].first)].push_back(v[i].second);
        h.push(max(day+1,v[i].first+1));
    }

    return 1;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>m>>d>>n;
    for (i=1;i<=n;i++){
        cin>>v[i].first;
        v[i].second = i;
    }

    sort (v+1,v+n+1);

    int st = 1, dr = n, sol;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif(mid)){
            sol = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    cout<<sol<<"\n";
    verif (sol);

    for (i=1;i<=m;i++){
        for (auto it : ans[i])
            cout<<it<<" ";
        cout<<"0\n";
    }



    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:54:16: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     cout<<sol<<"\n";
      |                ^~~~

• Subtask 1: 65 / 100