#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 |