oj.uz

Submission #419342

# Submission time Handle Problem Language Result Execution time Memory
419342 2021-06-07T01:29:35 Z freshmintt Job Scheduling (CEOI12_jobs) C++14
10 / 100
 446 ms 29608 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 < N; 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 < N; 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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 9140 KB Output isn't correct
2 Incorrect 38 ms 9208 KB Output isn't correct
3 Incorrect 38 ms 9208 KB Output isn't correct
4 Incorrect 38 ms 9140 KB Output isn't correct
5 Incorrect 37 ms 9140 KB Output isn't correct
6 Incorrect 37 ms 9212 KB Output isn't correct
7 Incorrect 38 ms 9268 KB Output isn't correct
8 Incorrect 39 ms 9140 KB Output isn't correct
9 Correct 204 ms 10692 KB Output is correct
10 Correct 209 ms 10708 KB Output is correct
11 Incorrect 34 ms 9132 KB Output isn't correct
12 Incorrect 72 ms 11468 KB Output isn't correct
13 Incorrect 93 ms 15540 KB Output isn't correct
14 Incorrect 146 ms 16304 KB Output isn't correct
15 Incorrect 172 ms 18452 KB Output isn't correct
16 Incorrect 210 ms 25656 KB Output isn't correct
17 Incorrect 252 ms 25748 KB Output isn't correct
18 Incorrect 259 ms 25668 KB Output isn't correct
19 Incorrect 446 ms 29608 KB Output isn't correct
20 Incorrect 238 ms 25768 KB Output isn't correct