oj.uz

Submission #418230

# Submission time Handle Problem Language Result Execution time Memory
418230 2021-06-05T08:34:07 Z freshmintt Job Scheduling (CEOI12_jobs) C++14
55 / 100
 302 ms 50088 KB 
#include<bits/stdc++.h>
#define MAXN 100005 //change. SET A SPACIOUS MAXN WHEN TESTING SO YOU DONT MESS UP WITH GARBAGE VALS OR SHIT
using namespace std;
typedef pair<long long,long long> pi;
typedef long long ll;
typedef long double ld;
ll N, D, M;

#define FIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
vector<ll> jobs;
vector<pi> jobs_save;
ll days[MAXN];
vector<ll> plan[MAXN];

bool make_plan(ll machs) {

  fill(days, days+MAXN, 0);

  for (int i=0; i < M; i++) {
    ll machID = i % machs;

    days[machID] = max(days[machID]+1, jobs_save[i].first); // ++ vs +1, obstructs with comparison.
    plan[days[machID]-1].push_back(jobs_save[i].second+1);
  }
  return true;
}

bool works(ll machs) {

  // cout << "trying: " << machs << endl;
  
  fill(days, days+MAXN, 0);

  for (int i=0; i < M; i++) {
    ll machID = i % machs;
    // cout << machID << " ";

    days[machID] = max(days[machID]+1, jobs[i]); // ++ vs +1, obstructs with comparison.

    // cout << jobs[i] << " for machine: "<< machID << " which has days: " << days[machID] << ". so diff: "<< (days[machID] - jobs[i]) << endl;

    if ((days[machID] - jobs[i]) > D){
      // cout <<"failed" << endl;
      return false;
    }
  }
  // cout <<"works" << endl;
  return true;
}

int main() { 
  // freopen("in", "r", stdin); // comment out
  FIO;
  cin >> N >> D >> M;

  
  for (int i = 0; i < M; i ++) {
    ll a; cin >> a; jobs.push_back(a); jobs_save.push_back({a,i});
  }

  sort(jobs.begin(), jobs.end());
  sort(jobs_save.begin(), jobs_save.end());

  ll a = 1; ll b = 1E9; ll mid;
  while (a != b) {
    mid = (a+b)/2;
    // cout << a << " and " << mid << " and " << b<< endl;

    if (works(mid)) {
      
      b = mid;
    }
    else {
      a = mid + 1;
    }
  }

  cout << a << endl;

  make_plan(a);
  for (ll i = 0; i < N; i++) {
    for (auto i : plan[i]) {
      cout << i << " ";
    }
    cout << "0" << endl;

  }
}

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7684 KB Output is correct
2 Correct 58 ms 7596 KB Output is correct
3 Correct 60 ms 7684 KB Output is correct
4 Correct 58 ms 7688 KB Output is correct
5 Correct 59 ms 7600 KB Output is correct
6 Correct 58 ms 7596 KB Output is correct
7 Correct 58 ms 7648 KB Output is correct
8 Correct 58 ms 7680 KB Output is correct
9 Correct 202 ms 7536 KB Output is correct
10 Correct 201 ms 7432 KB Output is correct
11 Correct 59 ms 7288 KB Output is correct
12 Runtime error 81 ms 16696 KB Execution killed with signal 11
13 Runtime error 113 ms 21492 KB Execution killed with signal 11
14 Runtime error 152 ms 26224 KB Execution killed with signal 11
15 Runtime error 175 ms 31012 KB Execution killed with signal 11
16 Runtime error 224 ms 35816 KB Execution killed with signal 11
17 Runtime error 255 ms 40508 KB Execution killed with signal 11
18 Runtime error 278 ms 46944 KB Execution killed with signal 11
19 Runtime error 302 ms 50088 KB Execution killed with signal 11
20 Runtime error 255 ms 40552 KB Execution killed with signal 11