Submission #448750

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
448750	2021-08-01T11:42:57 Z	chuangsheep	Job Scheduling (CEOI12_jobs)	C++11	50 / 100	759 ms	27008 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<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

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

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	332 ms	7320 KB	Output isn't correct
2	Incorrect	324 ms	7216 KB	Output isn't correct
3	Incorrect	345 ms	7264 KB	Output isn't correct
4	Incorrect	324 ms	7140 KB	Output isn't correct
5	Incorrect	323 ms	7224 KB	Output isn't correct
6	Incorrect	327 ms	7180 KB	Output isn't correct
7	Incorrect	326 ms	7320 KB	Output isn't correct
8	Incorrect	325 ms	7112 KB	Output isn't correct
9	Incorrect	146 ms	9992 KB	Output isn't correct
10	Incorrect	168 ms	10780 KB	Output isn't correct
11	Correct	58 ms	3588 KB	Output is correct
12	Correct	207 ms	5544 KB	Output is correct
13	Correct	209 ms	9172 KB	Output is correct
14	Correct	277 ms	11616 KB	Output is correct
15	Correct	296 ms	11536 KB	Output is correct
16	Correct	363 ms	18224 KB	Output is correct
17	Correct	447 ms	19356 KB	Output is correct
18	Correct	625 ms	19048 KB	Output is correct
19	Correct	759 ms	27008 KB	Output is correct
20	Correct	436 ms	19440 KB	Output is correct