oj.uz

Submission #419349

# Submission time Handle Problem Language Result Execution time Memory
419349 2021-06-07T01:39:35 Z freshmintt Job Scheduling (CEOI12_jobs) C++14
60 / 100
 628 ms 48680 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<int, int> pi;
typedef int 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 69 ms 30040 KB Output is correct
2 Correct 71 ms 30136 KB Output is correct
3 Correct 68 ms 30124 KB Output is correct
4 Correct 67 ms 30132 KB Output is correct
5 Correct 68 ms 30128 KB Output is correct
6 Correct 68 ms 30048 KB Output is correct
7 Correct 67 ms 30152 KB Output is correct
8 Correct 68 ms 30044 KB Output is correct
9 Correct 212 ms 30144 KB Output is correct
10 Correct 213 ms 30124 KB Output is correct
11 Correct 66 ms 29928 KB Output is correct
12 Correct 116 ms 32428 KB Output is correct
13 Runtime error 163 ms 35152 KB Memory limit exceeded
14 Runtime error 245 ms 37744 KB Memory limit exceeded
15 Runtime error 270 ms 38908 KB Memory limit exceeded
16 Runtime error 346 ms 41480 KB Memory limit exceeded
17 Runtime error 417 ms 45848 KB Memory limit exceeded
18 Runtime error 457 ms 46720 KB Memory limit exceeded
19 Runtime error 628 ms 48680 KB Memory limit exceeded
20 Runtime error 413 ms 45808 KB Memory limit exceeded