oj.uz

Submission #419360

# Submission time Handle Problem Language Result Execution time Memory
419360 2021-06-07T02:15:47 Z freshmintt Job Scheduling (CEOI12_jobs) C++14
60 / 100
 560 ms 46640 KB 
#include<bits/stdc++.h>
#define MAXN 1000000 //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;
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_save[i].first); // ++ vs +1, obstructs with comparison.
    if ((days[machID] - jobs_save[i].first) > D){
      return false;
    }
  }
  return true;
}

int main() { 
  FIO;
  // freopen("in", "r", stdin);
  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 65 ms 30012 KB Output is correct
2 Correct 66 ms 30016 KB Output is correct
3 Correct 67 ms 29964 KB Output is correct
4 Correct 68 ms 30008 KB Output is correct
5 Correct 67 ms 29944 KB Output is correct
6 Correct 66 ms 29968 KB Output is correct
7 Correct 70 ms 30020 KB Output is correct
8 Correct 67 ms 30004 KB Output is correct
9 Correct 215 ms 30020 KB Output is correct
10 Correct 215 ms 30080 KB Output is correct
11 Correct 62 ms 29904 KB Output is correct
12 Correct 124 ms 32312 KB Output is correct
13 Runtime error 152 ms 35184 KB Memory limit exceeded
14 Runtime error 220 ms 37596 KB Memory limit exceeded
15 Runtime error 234 ms 38360 KB Memory limit exceeded
16 Runtime error 291 ms 40476 KB Memory limit exceeded
17 Runtime error 357 ms 44388 KB Memory limit exceeded
18 Runtime error 381 ms 45044 KB Memory limit exceeded
19 Runtime error 560 ms 46640 KB Memory limit exceeded
20 Runtime error 357 ms 44588 KB Memory limit exceeded