oj.uz

답안 #419343

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
419343 2021-06-07T01:32:07 Z freshmintt Job Scheduling (CEOI12_jobs) C++14
0 / 100
 693 ms 65536 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<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 << 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 91 ms 35880 KB Memory limit exceeded
2 Runtime error 93 ms 35860 KB Memory limit exceeded
3 Runtime error 91 ms 35852 KB Memory limit exceeded
4 Runtime error 92 ms 35856 KB Memory limit exceeded
5 Runtime error 92 ms 35856 KB Memory limit exceeded
6 Runtime error 92 ms 35860 KB Memory limit exceeded
7 Runtime error 90 ms 35884 KB Memory limit exceeded
8 Runtime error 103 ms 35856 KB Memory limit exceeded
9 Runtime error 231 ms 35720 KB Memory limit exceeded
10 Runtime error 240 ms 35628 KB Memory limit exceeded
11 Runtime error 87 ms 35460 KB Memory limit exceeded
12 Runtime error 149 ms 39624 KB Memory limit exceeded
13 Runtime error 206 ms 44684 KB Memory limit exceeded
14 Runtime error 289 ms 49032 KB Memory limit exceeded
15 Runtime error 313 ms 50712 KB Memory limit exceeded
16 Runtime error 419 ms 55144 KB Memory limit exceeded
17 Runtime error 482 ms 62872 KB Memory limit exceeded
18 Runtime error 528 ms 64188 KB Memory limit exceeded
19 Runtime error 693 ms 65536 KB Memory limit exceeded
20 Runtime error 469 ms 62824 KB Memory limit exceeded