Submission #744289

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
744289	2023-05-18T10:29:56 Z	MODDI	Job Scheduling (CEOI12_jobs)	C++14	46 / 100	556 ms	20144 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;
	vi each_day[n+1];
	int job = m-1;
	for(int day = n; day >= 1; day--){
		int cnt = 0;
		while(job >= 0 && arr[job].first - day <= d && cnt + 1 <= ans){
			each_day[day].pb(arr[job].second);
			job--;
			cnt++;
		}
	}
	cout<<ans<<endl;
	for(int day = 1; day <= n; day++){
		for(auto t : each_day[day])
			cout<<t<<" ";
		cout<<0<<endl;
	}
	return 0;
}

Subtask #1

46.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	42 ms	2380 KB	Partially correct
2	Partially correct	45 ms	2352 KB	Partially correct
3	Partially correct	46 ms	2544 KB	Partially correct
4	Partially correct	41 ms	2356 KB	Partially correct
5	Partially correct	40 ms	2384 KB	Partially correct
6	Partially correct	47 ms	2364 KB	Partially correct
7	Partially correct	45 ms	2380 KB	Partially correct
8	Partially correct	42 ms	2444 KB	Partially correct
9	Partially correct	158 ms	4740 KB	Partially correct
10	Partially correct	162 ms	4684 KB	Partially correct
11	Partially correct	41 ms	2108 KB	Partially correct
12	Correct	82 ms	4160 KB	Output is correct
13	Partially correct	123 ms	6604 KB	Partially correct
14	Correct	230 ms	9036 KB	Output is correct
15	Partially correct	209 ms	9604 KB	Partially correct
16	Partially correct	286 ms	11920 KB	Partially correct
17	Partially correct	330 ms	15896 KB	Partially correct
18	Partially correct	341 ms	16340 KB	Partially correct
19	Partially correct	556 ms	20144 KB	Partially correct
20	Partially correct	322 ms	16020 KB	Partially correct