Submission #614835

#	Time	Username	Problem	Language	Result	Execution time	Memory
614835		Trytytka	Job Scheduling (CEOI12_jobs)	C++17	70 / 100	1064 ms	49568 KiB

jobs

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

long long n, d, m;
vector <pair<long long, long long>> a;

bool f(long long x){
	long long g;
	multiset<long long> b;
	for (long long i = 0; i < x; i++) b.insert(0);
	for (long long i = 0; i < m; i++){
		g=*b.begin();
		if(g-a[i].first>d||max(g, a[i].first)>n) return 0;
		b.erase(b.find(g));
		b.insert(max(g, a[i].first)+1);
	}
	return 1;
}

int main() {
	long long x=0, y=1;
	cin >> n >> d >> m;
	vector<set<long long>> c(n+1);
	a.resize(m);
	for (long long i = 0; i < m; i++) {cin >> a[i].first; a[i].second=i+1;}
	sort(a.begin(), a.end());
	while(!f(y)) y*=2;
	for (long long i = y/2; i>=1; i/=2){
		while(i+x<=y&&(!f(i+x))) x+=i;
	}
	cout << ++x;
	long long g;
	multiset<long long> b;
	for (long long i = 0; i < x; i++) b.insert(0);
	for (long long i = 0; i < m; i++){
		g=*b.begin();
		b.erase(b.find(g));
		b.insert(max(g, a[i].first)+1);
		c[max(g, a[i].first)].insert(a[i].second);
	}
	cout << endl;
	for (long long i = 1; i <= n; i++){
		for (auto j:c[i]){
			cout << j << ' ';
		}
		cout << 0 << endl;
	}
}

• Subtask 1: 70 / 100