Submission #429518

#	Time	Username	Problem	Language	Result	Execution time	Memory
429518		joshualiu555	Job Scheduling (CEOI12_jobs)	C++14	20 / 100	68 ms	3060 KiB

jobs

#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;
pair<int, int> a[INF], b[INF];

bool ok(int num_machines) {
    int current_day = 1;
    int current_index = 0;
    while (current_index < m) {
        for (int i = 0; i < num_machines && current_index < m; i++) {
            if (a[current_index].first + d < current_day) {
                return false;
            }
            current_index++;
        }
        current_day++;
    }
    return true;
}

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

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

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

    int left = 0, right = m;
    while (right > left + 1) {
        int middle = (left + right) / 2;
        if (ok(middle)) {
            right = middle;
        } else {
            left = middle;
        }
    }

    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: 20 / 100