Submission #1117466

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1117466	2024-11-23T18:24:02 Z	NAMIN	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	271 ms	28388 KB

jobs

/*
ID: NAMIN
TASK:
LANG: C++
*/
#include <iostream>
#include <numeric>
#include <math.h>
#include <set>
#include <unordered_set>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>
#include <fstream>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <deque>
#include <assert.h>

#define gcd __gcd
#define endl "\n"
#define ll long long

using namespace std;


void solve(){
	//ifstream cin("milkvisits.in");
	//ofstream cout("milkvisits.out");
	
	int n,d,m;
	cin >> n >> d >> m;
	vector<pair<int,int>> a(m);
	for(int i=0;i<m;i++){
		cin >> a[i].first;
		a[i].second = i;
	}
	
	sort(a.begin(),a.end());

	int ans = 1;
	int l = 1,r = 1e8;
	vector<int> day[n];
	while(l <= r){

		int x = l+(r-l)/2;

		bool ok = true;

		int cur_day = 1,cur_nb = 0;
		vector<int> day_temp[n];
		for(int i=0;i<m;i++){
			if(cur_day-a[i].first < 0){
				cur_day = a[i].first;
				cur_nb = 0;
			}
			else if(cur_nb == x){
				cur_day++;
				cur_nb = 0;
			}

			if(cur_day-a[i].first > d){
				ok = false;
				break;
			}

			cur_nb++;
			day_temp[cur_day-1].push_back(a[i].second+1);
		}

		if(ok && cur_day <= n){
			ans = x;
			r = x-1;
			for(int i=0;i<n;i++){
				day[i] = day_temp[i];
			}
		}
		else
			l = x+1;
	}

	cout << ans << endl;
	for(int i=0;i<n;i++){
		for(int x : day[i]){
			cout << x << ' ';
		}
		cout << "0\n";
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	//cin >> t;
 	while(t--){
		solve();
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	3648 KB	Output is correct
2	Correct	38 ms	3640 KB	Output is correct
3	Correct	40 ms	3640 KB	Output is correct
4	Correct	30 ms	3896 KB	Output is correct
5	Correct	32 ms	3800 KB	Output is correct
6	Correct	30 ms	3648 KB	Output is correct
7	Correct	31 ms	3648 KB	Output is correct
8	Correct	38 ms	3648 KB	Output is correct
9	Correct	38 ms	8016 KB	Output is correct
10	Correct	43 ms	8080 KB	Output is correct
11	Correct	34 ms	3400 KB	Output is correct
12	Correct	57 ms	6104 KB	Output is correct
13	Correct	97 ms	9288 KB	Output is correct
14	Correct	142 ms	13344 KB	Output is correct
15	Correct	131 ms	14268 KB	Output is correct
16	Correct	201 ms	17480 KB	Output is correct
17	Correct	234 ms	23112 KB	Output is correct
18	Correct	227 ms	23584 KB	Output is correct
19	Correct	271 ms	28388 KB	Output is correct
20	Correct	239 ms	23112 KB	Output is correct