#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl "\n"
struct Line {
int start, end;
};
int maxDelay;
vector<int> schedule;
vector<pair<int, int>> whine;
int n, m;
bool works(int machines) {
int index = 0;
int curmaxdelay = 0;
for (int i = 0; i < n; i++) {
int used = 0;
curmaxdelay = max(curmaxdelay, i - whine[index].first);
while (used < machines && index < m && whine[index].first <= i) {
//cout << whine[index].second << " ";
used++;
index++;
}
//cout << "0\n";
}
return curmaxdelay <= maxDelay;
}
// bool works(int machines) {
// deque<pair<int, int>> todo;
// int day = 0;
// int currentmaxdelay = 0;
// while (day < (int) schedule.size() || !todo.empty()) {
// todo.push_back({day, schedule[day]});
// currentmaxdelay = max(currentmaxdelay, day - todo.front().first);
// if (currentmaxdelay > maxDelay) return false;
// int machinesAvailible = machines;
// while (!todo.empty() && machinesAvailible > 0) {
// if (todo.front().second > machinesAvailible) {
// todo.front().second -= machinesAvailible;
// machinesAvailible = 0;
// } else {
// machinesAvailible -= todo.front().second;
// todo.pop_front();
// }
// }
// //cout << day << endl;
// day++;
// }
// return currentmaxdelay <= maxDelay;
// }
int main() {
// fast io
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
//freopen("snowboots.in", "r", stdin);
//freopen("snowboots.out", "w", stdout);
int d; cin >> n >> d >> m;
maxDelay = d;
schedule = vector<int>(n);
whine = vector<pair<int, int>>(m); // day, ID
for (int i = 0; i < m; i++) {
int temp; cin >> temp;
temp--;
schedule[temp]++;
whine[i] = {temp, i+1};
}
sort(whine.begin(), whine.end());
int lo = 1; int hi = 1e9;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if ((works[mid])) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
cout << lo + 1 << endl;
// this problem is a whiner who wants the answers to everything
int machines = lo + 1;
int index = 0;
for (int i = 0; i < n; i++) {
int used = 0;
while (used < machines && index < m && whine[index].first <= i) {
cout << whine[index].second << " ";
used++;
index++;
}
cout << "0\n";
}
}
Compilation message
jobs.cpp: In function 'int main()':
jobs.cpp:84:23: warning: pointer to a function used in arithmetic [-Wpointer-arith]
84 | if ((works[mid])) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1372 KB |
Output isn't correct |
| 2 |
Incorrect |
8 ms |
1372 KB |
Output isn't correct |
| 3 |
Incorrect |
7 ms |
1372 KB |
Output isn't correct |
| 4 |
Incorrect |
7 ms |
1288 KB |
Output isn't correct |
| 5 |
Incorrect |
7 ms |
1296 KB |
Output isn't correct |
| 6 |
Incorrect |
7 ms |
1296 KB |
Output isn't correct |
| 7 |
Incorrect |
8 ms |
1368 KB |
Output isn't correct |
| 8 |
Incorrect |
8 ms |
1372 KB |
Output isn't correct |
| 9 |
Incorrect |
19 ms |
2396 KB |
Output isn't correct |
| 10 |
Incorrect |
19 ms |
2396 KB |
Output isn't correct |
| 11 |
Incorrect |
12 ms |
1256 KB |
Output isn't correct |
| 12 |
Incorrect |
30 ms |
1884 KB |
Output isn't correct |
| 13 |
Incorrect |
38 ms |
2816 KB |
Output isn't correct |
| 14 |
Incorrect |
58 ms |
3668 KB |
Output isn't correct |
| 15 |
Incorrect |
65 ms |
4184 KB |
Output isn't correct |
| 16 |
Incorrect |
85 ms |
5188 KB |
Output isn't correct |
| 17 |
Incorrect |
96 ms |
5980 KB |
Output isn't correct |
| 18 |
Incorrect |
111 ms |
6764 KB |
Output isn't correct |
| 19 |
Incorrect |
130 ms |
9436 KB |
Output isn't correct |
| 20 |
Incorrect |
96 ms |
5980 KB |
Output isn't correct |
