oj.uz

Submission #405021

# Submission time Handle Problem Language Result Execution time Memory
405021 2021-05-15T14:59:18 Z aaravdodhia Job Scheduling (CEOI12_jobs) C++17
15 / 100
 646 ms 38196 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 3140 KB Output isn't correct
2 Incorrect 53 ms 3076 KB Output isn't correct
3 Incorrect 52 ms 3136 KB Output isn't correct
4 Incorrect 56 ms 3292 KB Output isn't correct
5 Incorrect 53 ms 3396 KB Output isn't correct
6 Incorrect 54 ms 3488 KB Output isn't correct
7 Incorrect 64 ms 3488 KB Output isn't correct
8 Incorrect 53 ms 3612 KB Output isn't correct
9 Incorrect 69 ms 5348 KB Output isn't correct
10 Incorrect 71 ms 5340 KB Output isn't correct
11 Incorrect 64 ms 4264 KB Output isn't correct
12 Correct 129 ms 8348 KB Output is correct
13 Incorrect 199 ms 13144 KB Output isn't correct
14 Correct 277 ms 19980 KB Output is correct
15 Incorrect 333 ms 19512 KB Output isn't correct
16 Correct 409 ms 32328 KB Output is correct
17 Runtime error 483 ms 35856 KB Memory limit exceeded
18 Incorrect 564 ms 32444 KB Output isn't correct
19 Runtime error 646 ms 38196 KB Memory limit exceeded
20 Runtime error 484 ms 35952 KB Memory limit exceeded