Submission #1083814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083814		NEMO_	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	294 ms	29108 KiB

jobs

#include <bits/stdc++.h>

#define ll long long
#define FAST                   \
	ios::sync_with_stdio(false); \
	cin.tie(NULL);
#define ld long double
// #define pb(x) push_back(x)
#define set(arr, x) memset(arr, x, sizeof(arr))
#define F0R(i, a) for (int i = 0; i < a; i++)
#define F1R(i, a) for (int i = 1; i <= a; i++)
#define all(x) (x).begin(), (x).end() // sort(all(vec))
// vec.resize(unique(all(vec)) - vec.begin());
// iota(p.begin(), p.end(), 0);

using namespace std;

int n, d, m;

pair<bool, vector<vector<int>>> valid(vector<pair<int, int>> &jobs, int mnMachine)
{
	vector<vector<int>> schedule(n);
	int need = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if(jobs[need].first > i) break;
			if(jobs[need].first + d >= i)
			{
				schedule[i - 1].push_back(jobs[need++].second);
			}
			else
			{
				make_pair(false, schedule);
			}
			if (need == m) return make_pair(true, schedule);
		}
	}
	return make_pair(false, schedule);
}
void solve()
{
	cin >> n >> d >> m;
	vector<pair<int, int>> jobs(m);
	for (int i = 0; i < m; i++)
	{
		cin >> jobs[i].first;
		jobs[i].second = i + 1;
	}
	sort(all(jobs));
	vector<vector<int>> result;
	int l = 1, r = m;
	while (l < r)
	{
		int mid = (l + r) / 2;
		pair<bool, vector<vector<int>>> res = valid(jobs, mid);
		if (res.first)
		{
			r = mid;
			result = res.second;
		}
		else
		{
			l = mid + 1;
		}
	}
	cout << l << endl;
	for (int i = 0; i < n; i++) {
		for (int &idx : result[i]) cout << idx << " ";
		cout << 0 << "\n";
	}
}

int main()
{
	FAST;
	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	};
	// solve();
	// cout << (2^4^5);
	return 0;
}

• Subtask 1: 0 / 100