Submission #1100347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100347		barkolorious	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	15 ms	13328 KiB

jobs

// 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 (stderr)

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: 0 / 100