Submission #600779

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
600779	2022-07-21T07:46:07 Z	as111	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	708 ms	65536 KB

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

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

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	91 ms	23244 KB	Output isn't correct
2	Incorrect	92 ms	23228 KB	Output isn't correct
3	Incorrect	95 ms	23244 KB	Output isn't correct
4	Incorrect	105 ms	23352 KB	Output isn't correct
5	Incorrect	95 ms	23300 KB	Output isn't correct
6	Incorrect	96 ms	23292 KB	Output isn't correct
7	Incorrect	95 ms	23296 KB	Output isn't correct
8	Incorrect	94 ms	23368 KB	Output isn't correct
9	Incorrect	215 ms	20084 KB	Output isn't correct
10	Incorrect	212 ms	20084 KB	Output isn't correct
11	Incorrect	79 ms	23960 KB	Output isn't correct
12	Runtime error	201 ms	38492 KB	Memory limit exceeded
13	Runtime error	265 ms	52892 KB	Memory limit exceeded
14	Runtime error	421 ms	65536 KB	Memory limit exceeded
15	Runtime error	343 ms	65536 KB	Execution killed with signal 9
16	Runtime error	564 ms	65536 KB	Execution killed with signal 9
17	Runtime error	605 ms	65536 KB	Execution killed with signal 9
18	Runtime error	506 ms	65536 KB	Execution killed with signal 9
19	Runtime error	583 ms	65536 KB	Execution killed with signal 9
20	Runtime error	708 ms	65536 KB	Execution killed with signal 9