제출 #990752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990752		IdanRosen	Job Scheduling (CEOI12_jobs)	C++98	0 / 100	1050 ms	49944 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 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();
}

컴파일 시 표준 에러 (stderr) 메시지

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