Submission #500941

#	Time	Username	Problem	Language	Result	Execution time	Memory
500941		omeganot	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	500 ms	16904 KiB

jobs

#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;
    }
  }
}

• Subtask 1: 100 / 100