Submission #405021

#	Time	Username	Problem	Language	Result	Execution time	Memory
405021		aaravdodhia	Job Scheduling (CEOI12_jobs)	C++17	15 / 100	646 ms	38196 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

int n, d, m;
vector<pair<int,int>> A;
vector<vector<int>> schedule;

bool works(int machines){
    for(int i=0; i<n; ++i) schedule[i].clear();
    int task = 0;
    for(int day = 0; day < n && task < m; task++){
        if(day > A[task].first + d){
            return false;
        }
        schedule[day].push_back(A[task].second);
        if(schedule[day].size() == machines){
            day++;
        }
    }
    return task == m; // dod we complete all m tasks within n days?
}

int main()
{
    cin >> n >> d >> m;
    A.resize(m);
    schedule.resize(n);

    for(int i=0; i<m; i++){
        cin >> A[i].first;
        A[i].second = i+1;
    }
    sort(begin(A), end(A));

    int lo = 1, hi = m;
    while(lo < hi){
        int mc = lo + (hi - lo)/2;
        if(works(mc)){
            hi = mc;
        } else{
            lo = mc + 1;
        }
    }

    if(works(lo)) cout << lo << '\n';
    for(vector<int> day: schedule){
        for(int task: day){
            cout << task << ' ';
        }
        cout << 0 << '\n';
    }
}

Compilation message (stderr)

jobs.cpp: In function 'bool works(int)':
jobs.cpp:17:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   17 |         if(schedule[day].size() == machines){
      |            ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 15 / 100