Submission #448772

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
448772	2021-08-01T12:44:57 Z	chuangsheep	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	474 ms	26404 KB

jobs

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

#define all(x) begin(x), end(x)
#define allr(x, r) begin(x), begin(x) + (r)
#define mp make_pair

using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

pair<bool, vector<vi>> isFeasible(const vector<pi> &jobs, int N, int D, int machineCount)
{
	vector<vi> res(N);
	int reqNum = 0;
	for (int day = 1; day <= N; day++)
	{
		for (int j = 0; j < machineCount; j++)
		{
			if (jobs.at(reqNum).first > day)
				break;
			if (jobs.at(reqNum).first + D >= day)
			{
				res[day - 1].push_back(jobs.at(reqNum++).second);
			}
			else
				return mp(false, res);
			if (reqNum == jobs.size())
				return mp(true, res);
		}
	}
	return mp(false, res);
}

int main()
{
#if defined(DEBUG) && !defined(ONLINE_JUDGE)
	// DEBUG
	cerr << "DEBUG flag set - see test.out for output\n";
	freopen("/home/chuang/shared-drives/F:/repos/cp/ois/ceoi12/test.in", "r", stdin);
	freopen("/home/chuang/shared-drives/F:/repos/cp/ois/ceoi12/test.out", "w", stdout);
#else
	cin.tie(0)->sync_with_stdio(false);
#endif

	int N, D, M;
	cin >> N >> D >> M;
	vector<pi> jobs(M);
	for (int i = 0; i < M; i++)
	{
		int day;
		cin >> day;
		jobs[i] = mp(day, i + 1);
	}
	sort(all(jobs));

	int l = 1, r = M / D + 1;
	vector<vi> res;
	while (l < r)
	{
		int mid = (l + r) / 2;
		pair<bool, vector<vi>> cur = isFeasible(jobs, N, D, mid);
		if (cur.first)
		{
			r = mid;
			res = cur.second;
		}
		else
			l = mid + 1;
	}

	cout << l << "\n";
	for (int i = 0; i < N; i++)
	{
		for (int &num : res[i])
			cout << num << " ";
		cout << 0 << "\n";
	}

	return 0;
}

Compilation message

jobs.cpp: In function 'std::pair<bool, std::vector<std::vector<int> > > isFeasible(const std::vector<std::pair<int, int> >&, int, int, int)':
jobs.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    if (reqNum == jobs.size())
      |        ~~~~~~~^~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	3152 KB	Output is correct
2	Correct	38 ms	3028 KB	Output is correct
3	Correct	39 ms	3116 KB	Output is correct
4	Correct	39 ms	3160 KB	Output is correct
5	Correct	38 ms	3152 KB	Output is correct
6	Correct	39 ms	3144 KB	Output is correct
7	Correct	38 ms	3048 KB	Output is correct
8	Correct	39 ms	3032 KB	Output is correct
9	Correct	120 ms	9656 KB	Output is correct
10	Correct	103 ms	9708 KB	Output is correct
11	Correct	43 ms	3136 KB	Output is correct
12	Correct	95 ms	4880 KB	Output is correct
13	Correct	124 ms	8568 KB	Output is correct
14	Correct	176 ms	10832 KB	Output is correct
15	Correct	243 ms	10876 KB	Output is correct
16	Correct	342 ms	17652 KB	Output is correct
17	Correct	335 ms	18636 KB	Output is correct
18	Correct	358 ms	18416 KB	Output is correct
19	Correct	474 ms	26404 KB	Output is correct
20	Correct	335 ms	18668 KB	Output is correct