Submission #990752

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
990752	2024-05-31T07:15:13 Z	IdanRosen	Job Scheduling (CEOI12_jobs)	C++	0 / 100	1000 ms	49944 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;
    vector<vector<ll>> best;
    while (start < end) {
        ll mid = start + (end - start) / 2;

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

    cout << start << "\n";
    for (int i = 1; i <= n; i++) {
        for (ll id: best[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	226 ms	7300 KB	Expected EOLN
2	Incorrect	206 ms	7356 KB	Expected EOLN
3	Incorrect	218 ms	7872 KB	Expected EOLN
4	Incorrect	211 ms	7256 KB	Expected EOLN
5	Incorrect	217 ms	7356 KB	Expected EOLN
6	Incorrect	209 ms	7868 KB	Expected EOLN
7	Incorrect	209 ms	7868 KB	Expected EOLN
8	Incorrect	213 ms	7612 KB	Expected EOLN
9	Incorrect	200 ms	17044 KB	Expected EOLN
10	Incorrect	183 ms	17504 KB	Expected EOLN
11	Incorrect	83 ms	5568 KB	Expected EOLN
12	Incorrect	238 ms	11040 KB	Expected EOLN
13	Incorrect	325 ms	16552 KB	Expected EOLN
14	Incorrect	451 ms	23796 KB	Expected EOLN
15	Incorrect	564 ms	25260 KB	Expected EOLN
16	Incorrect	501 ms	32348 KB	Expected EOLN
17	Runtime error	687 ms	40348 KB	Memory limit exceeded
18	Execution timed out	1020 ms	36004 KB	Time limit exceeded
19	Execution timed out	1050 ms	49944 KB	Time limit exceeded
20	Runtime error	659 ms	39500 KB	Memory limit exceeded