Submission #500941

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
500941	2022-01-01T17:49:50 Z	omeganot	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	500 ms	16904 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	1656 KB	Output is correct
2	Correct	45 ms	1732 KB	Output is correct
3	Correct	54 ms	1732 KB	Output is correct
4	Correct	39 ms	1720 KB	Output is correct
5	Correct	41 ms	1664 KB	Output is correct
6	Correct	41 ms	1708 KB	Output is correct
7	Correct	41 ms	1656 KB	Output is correct
8	Correct	44 ms	1684 KB	Output is correct
9	Correct	165 ms	1912 KB	Output is correct
10	Correct	158 ms	1856 KB	Output is correct
11	Correct	44 ms	1720 KB	Output is correct
12	Correct	86 ms	3640 KB	Output is correct
13	Correct	131 ms	5472 KB	Output is correct
14	Correct	193 ms	7804 KB	Output is correct
15	Correct	212 ms	9264 KB	Output is correct
16	Correct	318 ms	11816 KB	Output is correct
17	Correct	361 ms	13600 KB	Output is correct
18	Correct	346 ms	14772 KB	Output is correct
19	Correct	500 ms	16904 KB	Output is correct
20	Correct	352 ms	13684 KB	Output is correct