Submission #1271682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271682		cmiuc	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	169 ms	15052 KiB

jobs

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<pair<int, int>> s(1<<20);
int n, m, d;

bool verdict(int mid, bool print = 0){
	int lst = 0, R = 0;
	for (int i=1;i<=n;i++){
		while (s[R+1].first == i)
			R++;
		if (print == 1){
			for (int j=lst+1;j <= min(lst + mid, R);j++)
				cout<<s[j].second<<' ';
			cout<<"0\n";
		}

		lst = min(lst + mid, R);
		if (lst < m and s[lst+1].first + d <= i)
			return 0;
	}
	return 1;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>n>>d>>m;

	for (int i=1, j;i<=m;i++){
		cin>>j;
		s[i] = {j, i};
	}
	sort(begin(s) + 1, begin(s) + m + 1);

	int l = 0, r = m;
	while (l + 1 < r){
		int mid = (l + r) / 2;
		if (verdict(mid))
			r = mid;
		else
			l = mid;
	}
	cout<<r<<endl;
	verdict(r, 1);
}

• Subtask 1: 100 / 100