Submission #1012102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012102		ThommyDB	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	524 ms	25172 KiB

jobs

#include<bits/stdc++.h>

using namespace std;

int n, d, m;
vector<int> requests;
map<int,vector<int>> days;

bool possible(int machines){
    queue<int> q;
    for(int i = 0; i < n; i++){
        for(int job = 0; job < days[i].size(); job++){
            q.push(i);
        }
        for(int j = 0; j < machines; j++){
            if(q.empty())break;
            if(i-q.front() > d)return false;
            q.pop();
        }
    }
    if(q.empty()){
        return true;
    }
    return false;
}

signed main(){
    cin >> n >> d >> m;
    requests.resize(m);
    for(int i = 0; i < m; i++){
        cin >> requests[i];
        requests[i]--;
        days[requests[i]].push_back(i+1);
    }

    int machines = 0;
    int l = 1, r = 1e6;
    while(l < r){
        machines = r-(r-l)/2;
        //cout << l << "&&" << r << "&&" << machines << "\n";
        if(possible(machines)){
            r=machines-1;
        }
        else{
            l=machines;
        }
    }
    l++;
    cout << l << "\n";

    queue<pair<int, int>> q;
    for(int i = 0; i < n; i++){
        for(int job = 0; job < days[i].size(); job++){
            q.push({d, days[i][job]});
        }
        for(int j = 0; j < l; j++){
            if(q.empty())break;
            cout << q.front().second << " ";
            q.pop();
        }

        cout << "0\n";
    }
}

Compilation message (stderr)

jobs.cpp: In function 'bool possible(int)':
jobs.cpp:12:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for(int job = 0; job < days[i].size(); job++){
      |                          ~~~~^~~~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:53:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int job = 0; job < days[i].size(); job++){
      |                          ~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100