Submission #858469

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858469	2023-10-08T14:09:01 Z	ilef	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	197 ms	13908 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+1;
	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	13 ms	3164 KB	Output is correct
2	Correct	14 ms	3164 KB	Output is correct
3	Correct	15 ms	3216 KB	Output is correct
4	Correct	14 ms	3164 KB	Output is correct
5	Correct	14 ms	3164 KB	Output is correct
6	Correct	14 ms	3164 KB	Output is correct
7	Correct	14 ms	3160 KB	Output is correct
8	Correct	13 ms	3164 KB	Output is correct
9	Correct	25 ms	3420 KB	Output is correct
10	Correct	25 ms	3456 KB	Output is correct
11	Correct	20 ms	3164 KB	Output is correct
12	Correct	41 ms	3964 KB	Output is correct
13	Correct	62 ms	6480 KB	Output is correct
14	Correct	86 ms	7300 KB	Output is correct
15	Incorrect	107 ms	8016 KB	Output isn't correct
16	Correct	128 ms	10832 KB	Output is correct
17	Correct	151 ms	11604 KB	Output is correct
18	Correct	171 ms	12164 KB	Output is correct
19	Incorrect	197 ms	13908 KB	Output isn't correct
20	Correct	151 ms	11604 KB	Output is correct