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
#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) {
      |                ~~~~~~~~~^~~~~~~~~~~~~~~
# 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