Submission #448750

#	Time	Username	Problem	Language	Result	Execution time	Memory
448750		chuangsheep	Job Scheduling (CEOI12_jobs)	C++11	50 / 100	759 ms	27008 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<vector<int>>> isFeasible(const vector<pi> &jobs, int N, int D, int machineCount)
{
	set<pi> awaiting;
	vector<vi> plan(N);
	for (int i = 0, j = machineCount, d = 1; i < jobs.size(); i++)
	{
		if (d > N)
			return mp(false, plan);
		if (awaiting.size() != 0)
		{
			auto bg = awaiting.begin();
			if (j == 0)
			{
				d++;
				j = machineCount;
			}
			if ((*bg).first + D >= d)
			{
				j--;
				plan.at(d - 1).push_back((*bg).second);
				awaiting.erase(bg);
				i--;
				continue;
			}
			else
				return mp(false, plan);
		}

		if (jobs.at(i).first > d)
		{
			d = jobs.at(i).first;
			j = machineCount - 1;
			plan.at(d - 1).push_back(jobs.at(i).second);
		}
		else
		{
			if (j == 0)
			{
				awaiting.insert(jobs.at(i));
				while (i + 1 < jobs.size() && jobs.at(i + 1).first == jobs.at(i).first)
					awaiting.insert(jobs.at(++i));
			}
			else
			{
				if (jobs.at(i).first + D >= d)
				{
					j--;
					plan.at(d - 1).push_back(jobs.at(i).second);
				}
				else
					return mp(false, plan);
			}
		}
	}
	return mp(true, plan);
}

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:16:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for (int i = 0, j = machineCount, d = 1; i < jobs.size(); i++)
      |                                           ~~^~~~~~~~~~~~~
jobs.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while (i + 1 < jobs.size() && jobs.at(i + 1).first == jobs.at(i).first)
      |            ~~~~~~^~~~~~~~~~~~~

• Subtask 1: 50 / 100