Submission #858473

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858473	2023-10-08T14:12:30 Z	ilef	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	225 ms	13692 KB

jobs

#include <bits/stdc++.h>
using namespace std;
const int M=1e6+12;
int n,d,m;
 pair<int,int>a[M];
bool good(int num) {
     int i=0;
     int day=1;
     int cnt=0;
     while(i<m){
         if(cnt==num){
             cnt=0;
             day++;
         }
         if(a[i].first>day){
             day=a[i].first;
             cnt=0;
         }
         else if(a[i].first+d<day){
             return false;
         }
         i++;
         cnt++;
     }
     return day<=n;
}
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
	cin>>n>>d>>m;
   
	for(int i=0;i<m;i++){
	    cin>>a[i].first;
	    a[i].second=i;
	}
	sort(a,a+m);
	int l=1;
	int r=m;
	int mid=(l+r)/2;
	while(l<r){
	     mid=(l+r)/2;
	    if(good(mid)){
	        r=mid;
	    }
	    else{
	        l=mid+1;
	    }
	}
	int cnt=0;
	cout<<l<<"\n";
	int days=1;
	for(int i=0;i<m;i++){
	    if(a[i].first<=days){
	     cout<<a[i].second+1<<" ";
	     cnt++;
	      if(cnt==l){
	        cout<<0<<"\n";
	        cnt=0;
	        days++;}}
	         else{
	        cout<<0<<"\n";
	         days++;
	        cnt=0;
	         }
	    
	}
	for(int i=days;i<=n;i++){
	    cout<<0<<"\n";
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	3164 KB	Output is correct
2	Correct	13 ms	3164 KB	Output is correct
3	Correct	16 ms	3164 KB	Output is correct
4	Correct	13 ms	3160 KB	Output is correct
5	Correct	14 ms	3208 KB	Output is correct
6	Correct	13 ms	3164 KB	Output is correct
7	Correct	15 ms	3232 KB	Output is correct
8	Correct	13 ms	3164 KB	Output is correct
9	Correct	24 ms	3420 KB	Output is correct
10	Correct	24 ms	3416 KB	Output is correct
11	Correct	20 ms	3160 KB	Output is correct
12	Correct	41 ms	3952 KB	Output is correct
13	Correct	61 ms	6580 KB	Output is correct
14	Correct	87 ms	7300 KB	Output is correct
15	Correct	105 ms	8048 KB	Output is correct
16	Correct	128 ms	10868 KB	Output is correct
17	Correct	149 ms	11380 KB	Output is correct
18	Correct	167 ms	12140 KB	Output is correct
19	Correct	225 ms	13692 KB	Output is correct
20	Correct	150 ms	11600 KB	Output is correct