Submission #744290

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
744290	2023-05-18T10:32:53 Z	MODDI	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	482 ms	13884 KB

jobs

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, d, m;
vector<pii> arr;
bool check(int machines){
	ll day = 1 , cnt = 0 ;
    for(int i=0;i<m;i++){
        if(day < arr[i].first){
            day = arr[i].first ;
            cnt = 0 ;
        }
        if(day <= arr[i].first + d){ // do job i-th
            cnt++ ;
        }
        else {
            return false ;
        }
        if(cnt == machines){
            day++;
            cnt = 0 ;
        }
    }
 
    if(cnt == 0) day--;
 
    return day <= n ;
}
int main(){
	cin>>n>>d>>m;
	arr.resize(m);
	for(int i = 0; i < m; i++)
	{
		cin>>arr[i].first;
		arr[i].second = i+1;
	}
	sort(arr.begin(), arr.end());
	int l = 1, r = m, ans = 0;
	while(l <= r){
		int mid = (l + r) / 2;
		bool can = check(mid);
		if(can){
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
//	cout<<ans<<endl;
	cout<<ans<<endl;
	for(int i = 1, j = 0; i <= n; i++){
		for(int k = 0; j < m && k < ans; j++, k++)
			cout<<arr[j].second<<" ";
		cout<<0<<endl;
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	1620 KB	Output is correct
2	Correct	41 ms	1688 KB	Output is correct
3	Correct	41 ms	1680 KB	Output is correct
4	Correct	43 ms	1612 KB	Output is correct
5	Correct	45 ms	1616 KB	Output is correct
6	Correct	41 ms	1628 KB	Output is correct
7	Correct	48 ms	1596 KB	Output is correct
8	Correct	42 ms	1620 KB	Output is correct
9	Correct	156 ms	1852 KB	Output is correct
10	Correct	153 ms	1828 KB	Output is correct
11	Correct	46 ms	1584 KB	Output is correct
12	Correct	85 ms	3152 KB	Output is correct
13	Correct	122 ms	4568 KB	Output is correct
14	Correct	186 ms	6092 KB	Output is correct
15	Correct	201 ms	7544 KB	Output is correct
16	Correct	261 ms	9084 KB	Output is correct
17	Correct	317 ms	10508 KB	Output is correct
18	Correct	338 ms	12040 KB	Output is correct
19	Correct	482 ms	13884 KB	Output is correct
20	Correct	318 ms	10568 KB	Output is correct