// barkolorious - 13 October 2024
#include <bits/stdc++.h>
using namespace std;
#define FIN(x) freopen(x ".in", "r", stdin)
#define FOUT(x) freopen(x ".out", "w", stdout)
#define int long long
#define pb push_back
#define fr first
#define sc second
#define __ << " " <<
const int N = 2e5 + 5, M = 1e6 + 5;
int n, m, d;
vector<int> jobs[N];
int schedule[M];
int check (int machines) {
int ret = 0;
queue<int> q;
for (int i = 1; i <= n; i++) {
for (int job : jobs[i]) q.push(i);
int len = q.size();
for (int j = 0; j < min(len, machines); j++) {
int job = q.front(); q.pop();
ret = max(ret, i - job);
}
}
return ret;
}
void print_schedule (int machines) {
queue<int> q;
for (int i = 1; i <= n; i++) {
for (int job : jobs[i]) q.push(job);
int len = q.size();
for (int j = 0; j < min(len, machines); j++) {
int job = q.front(); q.pop();
cout << job << " ";
}
cout << 0 << endl;
}
}
void solve () {
cin >> n >> d >> m;
int max_jobs = 0;
for (int i = 1; i <= m; i++) {
cin >> schedule[i];
jobs[schedule[i]].pb(i);
max_jobs = max(max_jobs, (int) jobs[schedule[i]].size());
}
int l = 1, r = max_jobs;
while (l < r) {
int mid = (l + r) / 2;
if (check(mid) > d) l = mid + 1;
else r = mid;
}
cout << l << endl;
print_schedule(l);
}
/*
-- Sample 1 --
Input:
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
Output:
2
5 1 0
9 4 0
2 10 0
6 12 0
3 7 0
11 8 0
0
0
*/
/*
g++ -std=c++17 -O2 -Wall -DLOCAL "C:\Users\LENOVO\Desktop\BARKIN\Genel\Programming\Competitive\Questions\oj.uz\CEOI12\CEOI12_jobs.cpp" -o _run
*/
int32_t main () {
#ifndef LOCAL
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#endif
#ifdef LOCAL
clock_t __START__ = clock();
FILE* __FILE_IN__ = FIN("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
FILE* __FILE_OUT__ = FOUT("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
#else
#ifndef ONLINE_JUDGE
FILE* __FILE_IN__ = FIN("usaco");
FILE* __FILE_OUT__ = FOUT("usaco");
#endif
#endif
solve();
#ifdef LOCAL
fclose(__FILE_IN__);
fclose(__FILE_OUT__);
cerr << "Executed in: " << fixed << setprecision(3) << (double) (clock() - __START__) / CLOCKS_PER_SEC << "seconds" << endl;
#else
#ifndef ONLINE_JUDGE
fclose(__FILE_IN__);
fclose(__FILE_OUT__);
#endif
#endif
return 0;
}
Compilation message
jobs.cpp: In function 'long long int check(long long int)':
jobs.cpp:22:14: warning: unused variable 'job' [-Wunused-variable]
22 | for (int job : jobs[i]) q.push(i);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
13136 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
12 ms |
13136 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
12 ms |
13136 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
12 ms |
13136 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
12 ms |
13112 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
12 ms |
13136 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
11 ms |
13136 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
12 ms |
13136 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
15 ms |
13136 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
11 ms |
13136 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
11 ms |
13136 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
12 ms |
13136 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
13 ms |
13304 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
11 ms |
13136 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
13 ms |
13136 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
11 ms |
13312 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
12 ms |
13124 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
11 ms |
13136 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
12 ms |
13328 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
12 ms |
13136 KB |
Execution killed with signal 11 |
