oj.uz

Submission #1012100

# Submission time Handle Problem Language Result Execution time Memory
1012100 2024-07-01T16:04:17 Z ThommyDB Job Scheduling (CEOI12_jobs) C++17
40 / 100
 624 ms 32996 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(i);
        }
        for(int j = 0; j < machines; j++){
            if(q.empty())break;
            if(i+d-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 50 ms 3484 KB Output isn't correct
2 Incorrect 46 ms 3684 KB Output isn't correct
3 Incorrect 51 ms 3484 KB Output isn't correct
4 Incorrect 59 ms 3508 KB Output isn't correct
5 Incorrect 45 ms 3480 KB Output isn't correct
6 Incorrect 46 ms 3488 KB Output isn't correct
7 Incorrect 45 ms 3484 KB Output isn't correct
8 Incorrect 48 ms 3620 KB Output isn't correct
9 Incorrect 170 ms 10916 KB Output isn't correct
10 Incorrect 161 ms 11080 KB Output isn't correct
11 Correct 42 ms 2388 KB Output is correct
12 Correct 84 ms 4512 KB Output is correct
13 Correct 133 ms 7032 KB Output is correct
14 Correct 238 ms 10564 KB Output is correct
15 Correct 208 ms 10836 KB Output is correct
16 Correct 355 ms 15228 KB Output is correct
17 Correct 434 ms 17400 KB Output is correct
18 Incorrect 402 ms 22720 KB Output isn't correct
19 Runtime error 624 ms 32996 KB Memory limit exceeded
20 Correct 431 ms 17920 KB Output is correct