# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
990740 | IdanRosen | Job Scheduling (CEOI12_jobs) | C++98 | 1070 ms | 64676 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |