Submission #684617

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684617	2023-01-22T04:58:10 Z	randmac	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	331 ms	13768 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	34 ms	1612 KB	Output isn't correct
2	Incorrect	26 ms	1652 KB	Output isn't correct
3	Incorrect	27 ms	1728 KB	Output isn't correct
4	Incorrect	27 ms	1620 KB	Output isn't correct
5	Incorrect	26 ms	1736 KB	Output isn't correct
6	Incorrect	27 ms	1620 KB	Output isn't correct
7	Incorrect	26 ms	1720 KB	Output isn't correct
8	Incorrect	25 ms	1716 KB	Output isn't correct
9	Correct	141 ms	1880 KB	Output is correct
10	Correct	129 ms	1868 KB	Output is correct
11	Correct	24 ms	1616 KB	Output is correct
12	Correct	47 ms	3172 KB	Output is correct
13	Correct	73 ms	4600 KB	Output is correct
14	Correct	98 ms	6148 KB	Output is correct
15	Incorrect	120 ms	7556 KB	Output isn't correct
16	Correct	153 ms	9136 KB	Output is correct
17	Correct	176 ms	10544 KB	Output is correct
18	Correct	215 ms	12076 KB	Output is correct
19	Correct	331 ms	13768 KB	Output is correct
20	Correct	178 ms	10632 KB	Output is correct