제출 #502067

#제출 시각아이디문제언어결과실행 시간메모리
502067forevpurityJob Scheduling (CEOI12_jobs)C++17
100 / 100
471 ms13892 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
int n; int d; int m;
 
bool check(int x,vector<pair<int,int>>& jobs) {
  int j = 0;
  int maxdelay = 0;
  for(int i=1;i<=n;i++) {
	int machines = x;
    while(j<m&&jobs[j].first<=i&&machines>0) {
      machines--;
	  maxdelay = max(maxdelay,i-jobs[j].first);
	  j++;
	}
  }
  return maxdelay <= d;
}
 
int main() {
  cin >> n >> d >> m;
  vector<pair<int,int>> jobs(m,make_pair(0,0));
  for(int i=0;i<m;i++) {
    cin >> jobs[i].first;
	jobs[i].second = i+1;		
  }
  sort(jobs.begin(),jobs.end());
  int l = 1;
  int r = 100000;
  while(l<r) {
	  int mid = (l+r)/2;
      if(mid==l||mid==r) {
		  break;
	  }
	  if(check(mid,jobs)) {
		r = mid;
	  } else {
		l = mid;
	  }
  }
  if(check(l,jobs)) {
	int j = 0;
	cout << l << endl;
	for(int i=1;i<=n;i++) {
	  int machines = l;
      while(j<m&&jobs[j].first<=i&&machines>0) {
        machines--;
		cout << jobs[j].second << " ";
	    j++;
	  }
	  cout << 0 << endl;
    }
  } else {
	int j = 0;
	cout << r << endl;
    for(int i=1;i<=n;i++) {
	  int machines = r;
      while(j<m&&jobs[j].first<=i&&machines>0) {
        machines--;
		cout << jobs[j].second << " ";
	    j++;
	  }
	  cout << 0 << endl;
    }
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...