Submission #448772

#	Time	Username	Problem	Language	Result	Execution time	Memory
448772		chuangsheep	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	474 ms	26404 KiB

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 (stderr)

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 / 100