Submission #713436

#	Time	Username	Problem	Language	Result	Execution time	Memory
713436		magikrap	Job Scheduling (CEOI12_jobs)	C++14	15 / 100	424 ms	16964 KiB

jobs

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>

#define ll long long

using namespace std;

int N, D, M;
pair<int, int> arr[1000000];

bool check (int val) {
    //cout << "val: " << val << endl;
    int index = 0;
    for (int day = 1; day <= N; day++) {
        index += val;
        //cout << "day: " << day << " index: " << index << endl;
        if (index - 1 < M && arr[index - 1].first + D < day) {
            return false;
        } else if (index >= M) {
            return true;
        }
    }
    if (index >= M) {
        return true;
    } else {
        return false;
    }
}

void printAns (int val) {
    int index = 1;
    for (int day = 1; day <= N; day++) {
        for (int i = index; i < index + val && i <= M; i++) {
            cout << arr[i].second << " ";
        }
        index += val;
        cout << "0" << endl;
    }
}

int main() {
    cin >> N >> D >> M;
    for (int i = 1; i <= M; i++) {
        cin >> arr[i].first;
        arr[i].second = i;
    }
    sort(arr+1, arr + M+1, [](pair<int, int> a, pair<int, int> b) {
        return a.first < b.first;
    });
    // cout << "arr: " << endl;
    // for (int i = 1; i <= M; i++) {
    //     cout << arr[i].first << " " << arr[i].second << endl;
    // }
    int low = 1;
    int high = 1e7;
    while (low < high) {
        int mid = (low + high) / 2;
        if (check(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    cout << low << endl;
    printAns(low);
}

• Subtask 1: 15 / 100