Submission #990741

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
990741	2024-05-31T07:03:55 Z	IdanRosen	Job Scheduling (CEOI12_jobs)	C++	0 / 100	1000 ms	49828 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()) {
            // check if we can do the next range
            if (!(i < ranges[pq.top()].last)) return {};
            // do the 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	220 ms	7352 KB	Expected EOLN
2	Incorrect	220 ms	7868 KB	Expected EOLN
3	Incorrect	218 ms	7352 KB	Expected EOLN
4	Incorrect	213 ms	7400 KB	Expected EOLN
5	Incorrect	216 ms	8128 KB	Expected EOLN
6	Incorrect	209 ms	7356 KB	Expected EOLN
7	Incorrect	213 ms	7612 KB	Expected EOLN
8	Incorrect	211 ms	7616 KB	Expected EOLN
9	Incorrect	184 ms	16784 KB	Expected EOLN
10	Incorrect	185 ms	16916 KB	Expected EOLN
11	Incorrect	85 ms	5312 KB	Expected EOLN
12	Incorrect	248 ms	11184 KB	Expected EOLN
13	Incorrect	333 ms	18348 KB	Expected EOLN
14	Incorrect	434 ms	24496 KB	Expected EOLN
15	Incorrect	566 ms	25260 KB	Expected EOLN
16	Incorrect	484 ms	32420 KB	Expected EOLN
17	Runtime error	670 ms	41128 KB	Memory limit exceeded
18	Execution timed out	1036 ms	37280 KB	Time limit exceeded
19	Execution timed out	1028 ms	49828 KB	Time limit exceeded
20	Runtime error	679 ms	39364 KB	Memory limit exceeded