Submission #684613

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684613	2023-01-22T04:00:48 Z	randmac	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	337 ms	14024 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);

    // freopen("job-scheduling.in", "r", stdin);
    // freopen("job-scheduling.out", "w", stdout);

    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());
    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	29 ms	1636 KB	Output isn't correct
2	Incorrect	28 ms	1728 KB	Output isn't correct
3	Incorrect	28 ms	1724 KB	Output isn't correct
4	Incorrect	28 ms	1736 KB	Output isn't correct
5	Incorrect	30 ms	1752 KB	Output isn't correct
6	Incorrect	30 ms	1796 KB	Output isn't correct
7	Incorrect	33 ms	1752 KB	Output isn't correct
8	Incorrect	28 ms	1740 KB	Output isn't correct
9	Correct	135 ms	1868 KB	Output is correct
10	Correct	135 ms	1940 KB	Output is correct
11	Correct	30 ms	1740 KB	Output is correct
12	Correct	54 ms	3316 KB	Output is correct
13	Correct	72 ms	4792 KB	Output is correct
14	Correct	110 ms	6348 KB	Output is correct
15	Incorrect	124 ms	7864 KB	Output isn't correct
16	Correct	164 ms	9320 KB	Output is correct
17	Correct	209 ms	10848 KB	Output is correct
18	Correct	211 ms	12248 KB	Output is correct
19	Correct	337 ms	14024 KB	Output is correct
20	Correct	190 ms	10800 KB	Output is correct