oj.uz

Submission #418217

# Submission time Handle Problem Language Result Execution time Memory
418217 2021-06-05T08:27:13 Z freshmintt Job Scheduling (CEOI12_jobs) C++14
0 / 100
 288 ms 43740 KB 
#include<bits/stdc++.h>
#define MAXN 19 //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) {

  for (int i = 0; i < MAXN; i++) days[i] = 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;
  
  for (int i = 0; i < MAXN; i++) days[i] = 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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 5684 KB Execution killed with signal 11
2 Runtime error 19 ms 5648 KB Execution killed with signal 11
3 Runtime error 19 ms 5684 KB Execution killed with signal 11
4 Runtime error 19 ms 5680 KB Execution killed with signal 11
5 Runtime error 18 ms 5616 KB Execution killed with signal 11
6 Runtime error 19 ms 5620 KB Execution killed with signal 11
7 Runtime error 18 ms 5684 KB Execution killed with signal 11
8 Runtime error 19 ms 5588 KB Execution killed with signal 11
9 Runtime error 28 ms 5612 KB Execution killed with signal 11
10 Runtime error 28 ms 5684 KB Execution killed with signal 11
11 Runtime error 30 ms 5576 KB Execution killed with signal 11
12 Runtime error 62 ms 10348 KB Execution killed with signal 11
13 Runtime error 94 ms 15116 KB Execution killed with signal 11
14 Runtime error 134 ms 19876 KB Execution killed with signal 11
15 Runtime error 156 ms 24692 KB Execution killed with signal 11
16 Runtime error 211 ms 29340 KB Execution killed with signal 11
17 Runtime error 240 ms 34236 KB Execution killed with signal 11
18 Runtime error 253 ms 38884 KB Execution killed with signal 11
19 Runtime error 288 ms 43740 KB Execution killed with signal 11
20 Runtime error 238 ms 34284 KB Execution killed with signal 11