Submission #990740

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
990740	2024-05-31T07:02:01 Z	IdanRosen	Job Scheduling (CEOI12_jobs)	C++	0 / 100	1000 ms	64676 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 incraesing 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_job = 0;
    for (int i = 1; i <= no_days; i++) {
        while (next_job < ranges.size() && ranges[next_job].first <= i) {
            pq.push(next_job);
            next_job++;
        }

        ll curr_left = max_no_ranges_per_day;
        while (curr_left > 0 && !pq.empty()) {
            // do one range
            ans[i].push_back(ranges[pq.top()].id);
            pq.pop();
            curr_left--;
        }

        ans[i].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;
    });

    vector<vector<ll>> best_ans;
    ll min_days;

    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()) {
            min_days = mid;
            best_ans = ans;
            end = mid;
        } else
            start = mid + 1;
    }

    cout << min_days << "\n";
    for (int i = 1; i <= n; i++) {
        for (ll id: best_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:25: 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_job < ranges.size() && ranges[next_job].first <= i) {
      |                ~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	242 ms	12228 KB	Output isn't correct
2	Incorrect	238 ms	11960 KB	Output isn't correct
3	Incorrect	242 ms	12788 KB	Output isn't correct
4	Incorrect	251 ms	12216 KB	Output isn't correct
5	Incorrect	250 ms	11964 KB	Output isn't correct
6	Incorrect	235 ms	11964 KB	Output isn't correct
7	Incorrect	241 ms	12044 KB	Output isn't correct
8	Incorrect	241 ms	12732 KB	Output isn't correct
9	Incorrect	243 ms	20768 KB	Output isn't correct
10	Incorrect	242 ms	20748 KB	Output isn't correct
11	Incorrect	95 ms	6080 KB	Expected EOLN
12	Incorrect	253 ms	11704 KB	Expected EOLN
13	Incorrect	357 ms	18604 KB	Expected EOLN
14	Incorrect	490 ms	26408 KB	Expected EOLN
15	Incorrect	630 ms	27364 KB	Expected EOLN
16	Runtime error	585 ms	36260 KB	Memory limit exceeded
17	Runtime error	746 ms	44452 KB	Memory limit exceeded
18	Execution timed out	1070 ms	59304 KB	Time limit exceeded
19	Execution timed out	1016 ms	64676 KB	Time limit exceeded
20	Runtime error	701 ms	44712 KB	Memory limit exceeded