oj.uz

Submission #419345

# Submission time Handle Problem Language Result Execution time Memory
419345 2021-06-07T01:34:04 Z freshmintt Job Scheduling (CEOI12_jobs) C++14
60 / 100
 316 ms 56428 KB 
#include<bits/stdc++.h>
#define MAXN 200005 //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) {

  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.
    if ((days[machID] - jobs[i]) > D){
      return false;
    }
  }
  return true;
}

int main() { 
  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 = 1E6; 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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 10796 KB Output is correct
2 Correct 54 ms 10816 KB Output is correct
3 Correct 57 ms 10812 KB Output is correct
4 Correct 61 ms 10792 KB Output is correct
5 Correct 55 ms 10792 KB Output is correct
6 Correct 56 ms 10852 KB Output is correct
7 Correct 55 ms 10792 KB Output is correct
8 Correct 55 ms 10752 KB Output is correct
9 Correct 197 ms 10764 KB Output is correct
10 Correct 202 ms 10656 KB Output is correct
11 Correct 64 ms 10412 KB Output is correct
12 Correct 107 ms 14576 KB Output is correct
13 Runtime error 124 ms 27772 KB Execution killed with signal 11
14 Runtime error 161 ms 32652 KB Execution killed with signal 11
15 Runtime error 183 ms 37352 KB Execution killed with signal 11
16 Runtime error 240 ms 42080 KB Execution killed with signal 11
17 Runtime error 274 ms 46940 KB Execution killed with signal 11
18 Runtime error 287 ms 55336 KB Execution killed with signal 11
19 Runtime error 316 ms 56428 KB Execution killed with signal 11
20 Runtime error 268 ms 46912 KB Execution killed with signal 11