oj.uz

Submission #429502

# Submission time Handle Problem Language Result Execution time Memory
429502 2021-06-16T04:18:18 Z joshualiu555 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 307 ms 13756 KB 
#include <fstream>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

using ll = long long;
const int INF = 2e5 + 5;

int n, d, m;
vector<pair<int, int>> a;

bool ok (int machines) {
    int current_day = 1;
    int num_machines = 0;
    int current_job = 0;
    while (current_job < m) {
        if (a[current_job].first > current_day) {
            current_day++;
            num_machines = 0;
            continue;
        }
        if (current_day - a[current_job].first > d) {
            return false;
        }
        num_machines++;
        if (num_machines == machines) {
            current_day++;
            num_machines = 0;
        }
        current_job++;
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    //ifstream fin(".in");
    //ofstream fout(".out");

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

    int left = 0, right = 1000000;
    while (right > left + 1){
        int mid = (left + right) / 2;
        if (ok(mid)){
            right = mid;
        } else{
            left = mid;
        }
    }
    
    cout << right << "\n";
    int count = n;
    for (int i = 0; i < m; i += right){
        for (int j = i; j < min(m, i + right); j++){
            cout << a[j].second << " ";
        }
        count--;
        cout << 0 << "\n";
    }
    for (int i = 0; i < count; i++){
        cout << 0 << "\n";
    }

    return 0;
}

/*
 * 8 2 12
   1 2 4 2 1 3 5 6 1 3 6 4
*/

//

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1664 KB Output is correct
2 Correct 29 ms 1608 KB Output is correct
3 Correct 26 ms 1668 KB Output is correct
4 Correct 26 ms 1620 KB Output is correct
5 Correct 27 ms 1608 KB Output is correct
6 Correct 25 ms 1612 KB Output is correct
7 Correct 26 ms 1620 KB Output is correct
8 Correct 29 ms 1600 KB Output is correct
9 Correct 41 ms 1860 KB Output is correct
10 Correct 39 ms 1868 KB Output is correct
11 Correct 38 ms 1612 KB Output is correct
12 Correct 70 ms 3156 KB Output is correct
13 Correct 101 ms 4548 KB Output is correct
14 Correct 139 ms 6212 KB Output is correct
15 Correct 165 ms 7564 KB Output is correct
16 Correct 244 ms 9028 KB Output is correct
17 Correct 244 ms 10596 KB Output is correct
18 Correct 269 ms 11984 KB Output is correct
19 Correct 307 ms 13756 KB Output is correct
20 Correct 251 ms 10564 KB Output is correct