#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
const int DAY = 1e5+7;
int numDay, delay, numTask;
pair<int, int> beg[N];
vector<int> res[DAY];
bool isOk(int numWorker, bool isTrace = false) {
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
for (int i = 1, j = 1; i <= numDay; ++i) {
while (j <= numTask && beg[j].first == i) {
q.emplace(beg[j].first+delay, beg[j].second);
j++;
}
if (!q.empty() && q.top().first < i) {
return false;
}
int cnt = 0;
while (!q.empty() && ++cnt <= numWorker) {
if (isTrace) {
res[i].push_back(q.top().second);
}
q.pop();
}
}
return true;
}
int solve() {
int l = 1;
int r = numTask;
while (l < r) {
int m = l+r>>1;
if (isOk(m)) {
r = m;
} else {
l = m+1;
}
}
return l;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
#ifdef NHPHUCQT
freopen("demo.inp", "r", stdin);
freopen("demo.out", "w", stdout);
#endif
cin >> numDay >> delay >> numTask;
for (int i = 1; i <= numTask; ++i) {
cin >> beg[i].first;
beg[i].second = i;
}
sort(beg+1,beg+numTask+1);
// for (int i = 1; i <= numTask; ++i) {
// cerr << beg[i].first << ' ';
// }
// cerr << '\n';
int num = solve();
isOk(num, true);
cout << num << '\n';
for (int i = 1; i <= numDay; ++i) {
for (int x : res[i]) {
cout << x << ' ';
}
cout << 0 << '\n';
}
return 0;
}
Compilation message
jobs.cpp: In function 'int solve()':
jobs.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
36 | int m = l+r>>1;
| ~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
138 ms |
6992 KB |
Output is correct |
2 |
Correct |
146 ms |
7024 KB |
Output is correct |
3 |
Correct |
140 ms |
7120 KB |
Output is correct |
4 |
Correct |
138 ms |
7084 KB |
Output is correct |
5 |
Correct |
138 ms |
7020 KB |
Output is correct |
6 |
Correct |
141 ms |
7112 KB |
Output is correct |
7 |
Correct |
140 ms |
7132 KB |
Output is correct |
8 |
Correct |
138 ms |
7124 KB |
Output is correct |
9 |
Correct |
119 ms |
5980 KB |
Output is correct |
10 |
Correct |
136 ms |
6120 KB |
Output is correct |
11 |
Correct |
81 ms |
5744 KB |
Output is correct |
12 |
Correct |
256 ms |
7112 KB |
Output is correct |
13 |
Correct |
306 ms |
10668 KB |
Output is correct |
14 |
Correct |
388 ms |
12268 KB |
Output is correct |
15 |
Correct |
472 ms |
12372 KB |
Output is correct |
16 |
Correct |
391 ms |
15564 KB |
Output is correct |
17 |
Correct |
554 ms |
18496 KB |
Output is correct |
18 |
Execution timed out |
1014 ms |
18736 KB |
Time limit exceeded |
19 |
Execution timed out |
1048 ms |
14416 KB |
Time limit exceeded |
20 |
Correct |
552 ms |
18820 KB |
Output is correct |