Submission #429502

#	Time	Username	Problem	Language	Result	Execution time	Memory
429502		joshualiu555	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	307 ms	13756 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;
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 / 100