Submission #684617

#	Time	Username	Problem	Language	Result	Execution time	Memory
684617		randmac	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	331 ms	13768 KiB

jobs

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <queue>

using namespace std;

bool canFinish(vector<pair<int, int>> &a, int N, int D, int machines) {
    int available = machines;
    int day = 1;
    for (auto it = a.begin(); it != a.end(); it++) {
        if (available == 0) {
            day++;
            available = machines;
        }

        if (it->first + D >= day) {
            available--;
        } else {
            return false;
        }
    }

    // Take less than N days to finish all tasks
    return day <= N;
}

// https://oj.uz/problem/view/CEOI12_jobs
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, D, M;
    cin >> N >> D >> M;
    vector<pair<int, int>> a(M);
    for (int i = 0; i < M; i++) {
        cin >> a[i].first;
        a[i].second = i + 1;
    }

    sort(a.begin(), a.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
      if (a.first != b.first) {
        return a.first < b.first;
      } else {
        return b.second < a.second;
      }});

    int low = 1;
    int high = N;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (canFinish(a, N, D, mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    cout << low << endl;

    int available = low;
    int day = 1;
    for (auto it = a.begin(); it != a.end(); it++) {
        if (available == 0) {
            day++;
            available = low;
            cout << "0\n";
        }

        if (it->first + D >= day) {
            available--;
            cout << it->second << " ";
        } 
    }

    while (day <= N) {
        cout << "0";
        if (day < N) {
            cout << endl;
        }
        day++;
    }
}

• Subtask 1: 55 / 100