Submission #990744

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
990744	2024-05-31T07:10:33 Z	IdanRosen	Job Scheduling (CEOI12_jobs)	C++	0 / 100	1000 ms	36636 KB

jobs

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

struct range_t {
    ll id;

    // [first, last)
    ll first;
    ll last;
};

vector<vector<ll>> possible(const vector<range_t> &ranges/* sorted by increasing order of first day*/, ll no_days,
                            ll max_no_ranges_per_day) {
    vector<vector<ll>> ans(no_days + 1);

    auto comp = [&](ll left, ll right) -> bool {
        return !( // negation because of cpp priority queue
                ranges[left].last < ranges[right].last
        );
    };
    priority_queue<ll, vector<ll>, decltype(comp)> pq(comp);

    ll next_range = 0;
    for (int curr_day = 1; curr_day <= no_days; curr_day++) {
        while (next_range < ranges.size() && ranges[next_range].first <= curr_day) {
            pq.push(next_range);
            next_range++;
        }

        ll curr_left = max_no_ranges_per_day;
        while (curr_left > 0 && !pq.empty()) {
            // check if we can do the next range
            if (!(curr_day < ranges[pq.top()].last)) return {};
            // do the range
            ans[curr_day].push_back(ranges[pq.top()].id);
            pq.pop();
            curr_left--;
        }

        ans[curr_day].push_back(0);
    }

    if (pq.empty()) return ans;
    else return {};
}

void solve() {
    ll n, d, m;
    cin >> n >> d >> m;

    vector<range_t> ranges;
    for (int i = 1; i <= m; i++) {
        ll day;
        cin >> day;
        ranges.push_back({i, day, day + d + 1});
    }

    std::sort(ranges.begin(), ranges.end(), [](const range_t &left, const range_t &right) -> bool {
        return left.first < right.first;
    });


    ll start = 0;
    ll end = m + 1;
    while (start < end) {
        ll mid = start + (end - start) / 2;

        auto ans = possible(ranges, n, mid);
        if (!ans.empty()) {
            end = mid;
        } else
            start = mid + 1;
    }

    ll min_machines = start;
    auto ans = possible(ranges, n, min_machines);

    cout << min_machines << "\n";
    for (int i = 1; i <= n; i++) {
        for (ll id: ans[i])
            cout << id << " ";
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);

    solve();
}

Compilation message

jobs.cpp: In function 'std::vector<std::vector<long long int> > possible(const std::vector<range_t>&, ll, ll)':
jobs.cpp:31:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<range_t>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         while (next_range < ranges.size() && ranges[next_range].first <= curr_day) {
      |                ~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	230 ms	6080 KB	Expected EOLN
2	Incorrect	225 ms	5824 KB	Expected EOLN
3	Incorrect	225 ms	6080 KB	Expected EOLN
4	Incorrect	231 ms	6224 KB	Expected EOLN
5	Incorrect	242 ms	5820 KB	Expected EOLN
6	Incorrect	239 ms	5748 KB	Expected EOLN
7	Incorrect	229 ms	5824 KB	Expected EOLN
8	Incorrect	228 ms	5752 KB	Expected EOLN
9	Incorrect	184 ms	10636 KB	Expected EOLN
10	Incorrect	184 ms	10620 KB	Expected EOLN
11	Incorrect	92 ms	4560 KB	Expected EOLN
12	Incorrect	264 ms	9648 KB	Expected EOLN
13	Incorrect	348 ms	14840 KB	Expected EOLN
14	Incorrect	478 ms	18856 KB	Expected EOLN
15	Incorrect	601 ms	21120 KB	Expected EOLN
16	Incorrect	507 ms	26784 KB	Expected EOLN
17	Incorrect	687 ms	32464 KB	Expected EOLN
18	Execution timed out	1042 ms	29724 KB	Time limit exceeded
19	Execution timed out	1045 ms	36636 KB	Time limit exceeded
20	Incorrect	705 ms	32424 KB	Expected EOLN