Submission #600781

#	Time	Username	Problem	Language	Result	Execution time	Memory
600781		as111	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	802 ms	65536 KiB

jobs

#include <iostream>
#include <set>
#include<vector>

#define MAXN 100000

using namespace std;
int jobs[MAXN + 1];
multiset<int> curr; // currently working jobs
set<int> ID[MAXN + 1]; // all identifiers in the input for each day
set<int> ans[MAXN + 1]; // identifiers used in each day
int main() {
	int N, D, M;
	cin >> N >> D >> M;
	for (int m = 1; m <= M; m++) {
		int j;
		cin >> j;
		jobs[j] ++;
		ID[j].insert(m);
	}
	int low = 2;
	int high = 2;
	while (low == high) {
		int mid = (low + high) / 2; // bsearch on # of machines
		int mx = 0; // maximum delay occuring
		for (int i = 1; i <= N; i++) { // day i
			if(!curr.empty()) mx = max(mx, i - *curr.begin()); // number of days delay on earliest job
			if (curr.size() <= mid) {
				int left = mid - curr.size();
				curr.clear();
				for (int j = 1; j <= jobs[i] - left;j++) {
					curr.insert(i);
				}
			}
			else {
				set<int>::iterator it = curr.begin();
				advance(it, mid);
				curr.erase(curr.begin(), it);
				for (int j = 1; j <= jobs[i]; j++) {
					curr.insert(i);
				}
			}
		}
		if (mx <= D) {
			high = mid;
		}
		else {
			low = mid + 1;
		}
		if (low >= high) break;
	}
	set<int>::iterator it;
	int day = 0;
	for (int i = 1; i <= N; i++) { // day i
		if (curr.size() <= low) {
			int left = low - curr.size();
			for (int j = 1; j <= curr.size(); j++) {
				if (*curr.begin() != day) {
					day = *curr.begin();
					it = ID[day].begin();
				}
				curr.erase(curr.begin());
				ans[i].insert(*it); // add to job finished on this day
				it++;
			}
			day = i;
			it = ID[day].begin();
			for (int j = 1; j <= jobs[i]; j++) {
				if (j > jobs[i] - left) {
					ans[i].insert(*it);
					it++;
				}
				else {
					curr.insert(i);
				}
			}
		}
		else {
			for (int j = 1; j <= low; j++) {
				if (*curr.begin() != day) {
					day = *curr.begin();
					it = ID[day].begin();
				}
				curr.erase(curr.begin());
				ans[i].insert(*it);
				it++;
			}
			for (int j = 1; j <= jobs[i]; j++) {
				curr.insert(i);
			}
		}
	}
	cout << low << endl;
	for (int i = 1; i <= N; i++) {
		for (int e : ans[i]) {
			cout << e << " ";
		}
		cout << 0 << endl;
	}
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:28:20: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |    if (curr.size() <= mid) {
      |        ~~~~~~~~~~~~^~~~~~
jobs.cpp:55:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |   if (curr.size() <= low) {
      |       ~~~~~~~~~~~~^~~~~~
jobs.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    for (int j = 1; j <= curr.size(); j++) {
      |                    ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 100