Submission #858472

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858472	2023-10-08T14:10:05 Z	ilef	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	196 ms	13888 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;
         }
         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

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	3164 KB	Output is correct
2	Correct	16 ms	3164 KB	Output is correct
3	Correct	14 ms	3164 KB	Output is correct
4	Correct	13 ms	3164 KB	Output is correct
5	Correct	13 ms	3204 KB	Output is correct
6	Correct	14 ms	3164 KB	Output is correct
7	Correct	14 ms	3164 KB	Output is correct
8	Correct	14 ms	3416 KB	Output is correct
9	Correct	24 ms	3420 KB	Output is correct
10	Correct	24 ms	3420 KB	Output is correct
11	Correct	20 ms	3164 KB	Output is correct
12	Correct	41 ms	3920 KB	Output is correct
13	Correct	63 ms	6480 KB	Output is correct
14	Correct	87 ms	7248 KB	Output is correct
15	Incorrect	115 ms	8272 KB	Output isn't correct
16	Correct	128 ms	10876 KB	Output is correct
17	Correct	161 ms	11604 KB	Output is correct
18	Correct	175 ms	12156 KB	Output is correct
19	Incorrect	196 ms	13888 KB	Output isn't correct
20	Correct	150 ms	11604 KB	Output is correct