oj.uz

Submission #419340

# Submission time Handle Problem Language Result Execution time Memory
419340 2021-06-07T01:12:56 Z freshmintt Job Scheduling (CEOI12_jobs) C++14
0 / 100
 324 ms 56344 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 < 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 = 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 << "1";
  return 0;

  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 Incorrect 35 ms 9140 KB Output isn't correct
2 Incorrect 36 ms 9132 KB Output isn't correct
3 Incorrect 35 ms 9064 KB Output isn't correct
4 Incorrect 35 ms 9132 KB Output isn't correct
5 Incorrect 36 ms 9140 KB Output isn't correct
6 Incorrect 36 ms 9140 KB Output isn't correct
7 Incorrect 37 ms 9148 KB Output isn't correct
8 Incorrect 37 ms 9116 KB Output isn't correct
9 Incorrect 44 ms 9124 KB Output isn't correct
10 Incorrect 45 ms 9128 KB Output isn't correct
11 Incorrect 51 ms 9080 KB Output isn't correct
12 Incorrect 95 ms 11424 KB Output isn't correct
13 Runtime error 138 ms 27772 KB Execution killed with signal 6
14 Runtime error 172 ms 32636 KB Execution killed with signal 6
15 Runtime error 194 ms 37356 KB Execution killed with signal 6
16 Runtime error 244 ms 42136 KB Execution killed with signal 6
17 Runtime error 278 ms 46864 KB Execution killed with signal 6
18 Runtime error 291 ms 51696 KB Execution killed with signal 11
19 Runtime error 324 ms 56344 KB Execution killed with signal 6
20 Runtime error 276 ms 47028 KB Execution killed with signal 6