Submission #990741

#	Time	Username	Problem	Language	Result	Execution time	Memory
990741		IdanRosen	Job Scheduling (CEOI12_jobs)	C++98	0 / 100	1036 ms	49828 KiB

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 (stderr)

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