oj.uz

Submission #419344

# Submission time Handle Problem Language Result Execution time Memory
419344 2021-06-07T01:32:52 Z freshmintt Job Scheduling (CEOI12_jobs) C++14
60 / 100
 334 ms 56448 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 = 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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 10788 KB Output is correct
2 Correct 62 ms 10792 KB Output is correct
3 Correct 62 ms 10820 KB Output is correct
4 Correct 61 ms 10792 KB Output is correct
5 Correct 61 ms 10836 KB Output is correct
6 Correct 61 ms 10804 KB Output is correct
7 Correct 60 ms 10792 KB Output is correct
8 Correct 63 ms 10804 KB Output is correct
9 Correct 206 ms 10760 KB Output is correct
10 Correct 200 ms 10664 KB Output is correct
11 Correct 60 ms 10536 KB Output is correct
12 Correct 117 ms 14540 KB Output is correct
13 Runtime error 136 ms 27772 KB Execution killed with signal 11
14 Runtime error 173 ms 32620 KB Execution killed with signal 11
15 Runtime error 193 ms 37384 KB Execution killed with signal 11
16 Runtime error 246 ms 42172 KB Execution killed with signal 11
17 Runtime error 277 ms 46884 KB Execution killed with signal 11
18 Runtime error 301 ms 55384 KB Execution killed with signal 11
19 Runtime error 334 ms 56448 KB Execution killed with signal 11
20 Runtime error 284 ms 46900 KB Execution killed with signal 11