Submission #448765

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
448765	2021-08-01T12:32:53 Z	chuangsheep	Job Scheduling (CEOI12_jobs)	C++11	50 / 100	774 ms	27068 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);
	int d = 1;
	for (int i = 0, j = machineCount; 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(d <= N, 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:17:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for (int i = 0, j = machineCount; i < jobs.size(); i++)
      |                                    ~~^~~~~~~~~~~~~
jobs.cpp:52: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]
   52 |     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	329 ms	7132 KB	Output isn't correct
2	Incorrect	346 ms	7204 KB	Output isn't correct
3	Incorrect	337 ms	7128 KB	Output isn't correct
4	Incorrect	322 ms	7212 KB	Output isn't correct
5	Incorrect	323 ms	7184 KB	Output isn't correct
6	Incorrect	319 ms	7220 KB	Output isn't correct
7	Incorrect	350 ms	7132 KB	Output isn't correct
8	Incorrect	326 ms	7216 KB	Output isn't correct
9	Incorrect	144 ms	9944 KB	Output isn't correct
10	Incorrect	175 ms	10812 KB	Output isn't correct
11	Correct	57 ms	3524 KB	Output is correct
12	Correct	192 ms	5576 KB	Output is correct
13	Correct	219 ms	9108 KB	Output is correct
14	Correct	276 ms	11584 KB	Output is correct
15	Correct	295 ms	11500 KB	Output is correct
16	Correct	375 ms	18284 KB	Output is correct
17	Correct	440 ms	19224 KB	Output is correct
18	Correct	623 ms	18880 KB	Output is correct
19	Correct	774 ms	27068 KB	Output is correct
20	Correct	430 ms	19248 KB	Output is correct