Submission #1117466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117466		NAMIN	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	271 ms	28388 KiB

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 / 100