oj.uz

Submission #1100350

# Submission time Handle Problem Language Result Execution time Memory
1100350 2024-10-13T14:42:47 Z barkolorious Job Scheduling (CEOI12_jobs) C++17
100 / 100
 262 ms 28476 KB 
// 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
*/

int32_t main () {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  solve();
  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);
      |              ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 10956 KB Output is correct
2 Correct 30 ms 10956 KB Output is correct
3 Correct 38 ms 10948 KB Output is correct
4 Correct 31 ms 10956 KB Output is correct
5 Correct 31 ms 11088 KB Output is correct
6 Correct 32 ms 10956 KB Output is correct
7 Correct 31 ms 10952 KB Output is correct
8 Correct 30 ms 10956 KB Output is correct
9 Correct 154 ms 10864 KB Output is correct
10 Correct 154 ms 10920 KB Output is correct
11 Correct 17 ms 10500 KB Output is correct
12 Correct 28 ms 12380 KB Output is correct
13 Correct 45 ms 17432 KB Output is correct
14 Correct 78 ms 18948 KB Output is correct
15 Correct 70 ms 20468 KB Output is correct
16 Correct 109 ms 24752 KB Output is correct
17 Correct 122 ms 27872 KB Output is correct
18 Correct 120 ms 27444 KB Output is correct
19 Correct 262 ms 28476 KB Output is correct
20 Correct 128 ms 27872 KB Output is correct