oj.uz

Submission #405013

# Submission time Handle Problem Language Result Execution time Memory
405013 2021-05-15T14:47:39 Z aaravdodhia Job Scheduling (CEOI12_jobs) C++17
15 / 100
 547 ms 38184 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;){
        if(task == m || schedule[day].size() == machines){
            day++;
            continue;
        }
        if(day > A[task].first + d) return false;
        schedule[day].push_back(A[task].second);
        task++;
    }
    return task == m;
}

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:13:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |         if(task == m || schedule[day].size() == machines){
      |                         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 3108 KB Output isn't correct
2 Incorrect 56 ms 3064 KB Output isn't correct
3 Incorrect 46 ms 3232 KB Output isn't correct
4 Incorrect 46 ms 3368 KB Output isn't correct
5 Incorrect 46 ms 3400 KB Output isn't correct
6 Incorrect 49 ms 3492 KB Output isn't correct
7 Incorrect 48 ms 3540 KB Output isn't correct
8 Incorrect 51 ms 3612 KB Output isn't correct
9 Incorrect 65 ms 5316 KB Output isn't correct
10 Incorrect 65 ms 5344 KB Output isn't correct
11 Incorrect 59 ms 4324 KB Output isn't correct
12 Correct 116 ms 8268 KB Output is correct
13 Incorrect 208 ms 13240 KB Output isn't correct
14 Correct 251 ms 19908 KB Output is correct
15 Incorrect 286 ms 19660 KB Output isn't correct
16 Correct 371 ms 32408 KB Output is correct
17 Runtime error 487 ms 35772 KB Memory limit exceeded
18 Incorrect 470 ms 32444 KB Output isn't correct
19 Runtime error 547 ms 38184 KB Memory limit exceeded
20 Runtime error 441 ms 35820 KB Memory limit exceeded