oj.uz

Submission #419346

# Submission time Handle Problem Language Result Execution time Memory
419346 2021-06-07T01:38:06 Z freshmintt Job Scheduling (CEOI12_jobs) C++14
0 / 100
 637 ms 65536 KB 
#include<bits/stdc++.h>
#define MAXN 1000005 //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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 80 ms 35988 KB Memory limit exceeded
2 Runtime error 81 ms 35836 KB Memory limit exceeded
3 Runtime error 78 ms 35852 KB Memory limit exceeded
4 Runtime error 79 ms 35884 KB Memory limit exceeded
5 Runtime error 78 ms 35904 KB Memory limit exceeded
6 Runtime error 80 ms 35840 KB Memory limit exceeded
7 Runtime error 80 ms 35876 KB Memory limit exceeded
8 Runtime error 78 ms 35860 KB Memory limit exceeded
9 Runtime error 223 ms 35756 KB Memory limit exceeded
10 Runtime error 223 ms 35704 KB Memory limit exceeded
11 Runtime error 78 ms 35472 KB Memory limit exceeded
12 Runtime error 131 ms 39612 KB Memory limit exceeded
13 Runtime error 178 ms 44632 KB Memory limit exceeded
14 Runtime error 260 ms 48928 KB Memory limit exceeded
15 Runtime error 277 ms 50716 KB Memory limit exceeded
16 Runtime error 360 ms 55004 KB Memory limit exceeded
17 Runtime error 431 ms 62884 KB Memory limit exceeded
18 Runtime error 456 ms 64060 KB Memory limit exceeded
19 Runtime error 637 ms 65536 KB Memory limit exceeded
20 Runtime error 434 ms 62824 KB Memory limit exceeded