oj.uz

답안 #1100347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100347 2024-10-13T14:41:18 Z barkolorious Job Scheduling (CEOI12_jobs) C++17
0 / 100
 15 ms 13328 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
*/

/*
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);
      |              ^~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 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