oj.uz

답안 #418225

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418225 2021-06-05T08:30:48 Z freshmintt Job Scheduling (CEOI12_jobs) C++14
55 / 100
 311 ms 50012 KB 
#include<bits/stdc++.h>
#define MAXN 100005 //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) {

  for (int i = 0; i < MAXN; i++) days[i] = 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) {

  // cout << "trying: " << machs << endl;
  
  for (int i = 0; i < MAXN; i++) days[i] = 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.

    // cout << jobs[i] << " for machine: "<< machID << " which has days: " << days[machID] << ". so diff: "<< (days[machID] - jobs[i]) << endl;

    if ((days[machID] - jobs[i]) > D){
      // cout <<"failed" << endl;
      return false;
    }
  }
  // cout <<"works" << endl;
  return true;
}

int main() { 
  // freopen("in", "r", stdin); // comment out
  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
55.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 7696 KB Output is correct
2 Correct 68 ms 7632 KB Output is correct
3 Correct 60 ms 7680 KB Output is correct
4 Correct 63 ms 7676 KB Output is correct
5 Correct 59 ms 7624 KB Output is correct
6 Correct 60 ms 7692 KB Output is correct
7 Correct 59 ms 7632 KB Output is correct
8 Correct 63 ms 7704 KB Output is correct
9 Correct 202 ms 7460 KB Output is correct
10 Correct 209 ms 7440 KB Output is correct
11 Correct 59 ms 7332 KB Output is correct
12 Runtime error 85 ms 16664 KB Execution killed with signal 11
13 Runtime error 117 ms 21516 KB Execution killed with signal 11
14 Runtime error 159 ms 26264 KB Execution killed with signal 11
15 Runtime error 181 ms 31012 KB Execution killed with signal 11
16 Runtime error 230 ms 35720 KB Execution killed with signal 11
17 Runtime error 262 ms 40588 KB Execution killed with signal 11
18 Runtime error 282 ms 46920 KB Execution killed with signal 11
19 Runtime error 311 ms 50012 KB Execution killed with signal 11
20 Runtime error 267 ms 40552 KB Execution killed with signal 11