oj.uz

Submission #1012096

# Submission time Handle Problem Language Result Execution time Memory
1012096 2024-07-01T16:00:17 Z ThommyDB Job Scheduling (CEOI12_jobs) C++17
40 / 100
 639 ms 33048 KB 
#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(d);
        }
        for(int j = 0; j < machines; j++){
            if(q.empty())break;
            if(q.front() < 0)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

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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 3692 KB Output isn't correct
2 Incorrect 50 ms 3480 KB Output isn't correct
3 Incorrect 50 ms 3484 KB Output isn't correct
4 Incorrect 48 ms 3736 KB Output isn't correct
5 Incorrect 46 ms 3528 KB Output isn't correct
6 Incorrect 48 ms 3480 KB Output isn't correct
7 Incorrect 48 ms 3480 KB Output isn't correct
8 Incorrect 47 ms 3484 KB Output isn't correct
9 Incorrect 186 ms 10968 KB Output isn't correct
10 Incorrect 180 ms 10880 KB Output isn't correct
11 Correct 42 ms 2412 KB Output is correct
12 Correct 85 ms 4460 KB Output is correct
13 Correct 123 ms 6992 KB Output is correct
14 Correct 268 ms 10632 KB Output is correct
15 Correct 224 ms 10836 KB Output is correct
16 Correct 370 ms 15264 KB Output is correct
17 Correct 438 ms 17408 KB Output is correct
18 Incorrect 417 ms 22836 KB Output isn't correct
19 Runtime error 639 ms 33048 KB Memory limit exceeded
20 Correct 429 ms 17916 KB Output is correct