Submission #502067

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
502067	2022-01-05T08:06:15 Z	forevpurity	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	471 ms	13892 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	50 ms	1740 KB	Output is correct
2	Correct	41 ms	1732 KB	Output is correct
3	Correct	42 ms	1732 KB	Output is correct
4	Correct	40 ms	1728 KB	Output is correct
5	Correct	52 ms	1736 KB	Output is correct
6	Correct	54 ms	1724 KB	Output is correct
7	Correct	40 ms	1728 KB	Output is correct
8	Correct	50 ms	1648 KB	Output is correct
9	Correct	170 ms	1884 KB	Output is correct
10	Correct	147 ms	1852 KB	Output is correct
11	Correct	43 ms	1692 KB	Output is correct
12	Correct	82 ms	3304 KB	Output is correct
13	Correct	115 ms	4696 KB	Output is correct
14	Correct	185 ms	6236 KB	Output is correct
15	Correct	207 ms	7672 KB	Output is correct
16	Correct	270 ms	9144 KB	Output is correct
17	Correct	341 ms	10736 KB	Output is correct
18	Correct	335 ms	12136 KB	Output is correct
19	Correct	471 ms	13892 KB	Output is correct
20	Correct	305 ms	10712 KB	Output is correct