Submission #1083814

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1083814	2024-09-04T08:02:39 Z	NEMO_	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	294 ms	29108 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	28 ms	3660 KB	Output isn't correct
2	Incorrect	28 ms	3760 KB	Output isn't correct
3	Incorrect	27 ms	3660 KB	Output isn't correct
4	Incorrect	27 ms	3744 KB	Output isn't correct
5	Incorrect	27 ms	3668 KB	Output isn't correct
6	Incorrect	26 ms	3760 KB	Output isn't correct
7	Incorrect	27 ms	3668 KB	Output isn't correct
8	Incorrect	38 ms	3740 KB	Output isn't correct
9	Incorrect	67 ms	10068 KB	Output isn't correct
10	Incorrect	58 ms	10096 KB	Output isn't correct
11	Incorrect	28 ms	3348 KB	Output isn't correct
12	Incorrect	56 ms	5792 KB	Output isn't correct
13	Incorrect	79 ms	9816 KB	Output isn't correct
14	Incorrect	140 ms	12192 KB	Output isn't correct
15	Incorrect	141 ms	12936 KB	Output isn't correct
16	Incorrect	210 ms	17332 KB	Output isn't correct
17	Incorrect	239 ms	21300 KB	Output isn't correct
18	Incorrect	241 ms	20812 KB	Output isn't correct
19	Incorrect	294 ms	29108 KB	Output isn't correct
20	Incorrect	230 ms	21252 KB	Output isn't correct