제출 #418225

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
418225		freshmintt	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	311 ms	50012 KiB

jobs

#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 / 100