Submission #63346

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
63346	2018-08-01T14:03:50 Z	bazsi700	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	448 ms	13740 KB

jobs

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL

//15:55 -1 óra? fél?

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,d,m;
	cin >> n >> d >> m;
	vii jobs(n+1,vi());
	for(int i = 0; i < m; i++) {
		int x;
		cin >> x;
		jobs[x].push_back(i+1);
	}
	int l = 1;
	int r = m;
	while(l < r) {
		int mid = (l+r)/2;
		queue<int> todo;
		bool good = true;
		for(int i = 1; i <= n; i++) {
			for(int j = 0; j < jobs[i].size(); j++) {
				todo.push(i);
			}
			for(int j = 0; j < mid; j++) {
				if(todo.empty()) {
					break;
				}
				int day = todo.front();
				todo.pop();
				if(day+d < i) {
					good = false;
					break;
				}
			}
			if(!good) {
				break;
			}
		}
		if(good) {
			r = mid;
		} else {
			l = mid+1;
		}
	}
	cout << l << "\n";
	queue<int> todo;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < jobs[i].size(); j++) {
			todo.push(jobs[i][j]);
		}
		for(int j = 0; j < l; j++) {
			if(todo.empty()) {
				break;
			}
			int id = todo.front();
			todo.pop();
			cout << id << " ";
		}
		cout << "0\n";
	}
	return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:31:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < jobs[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~~
jobs.cpp:58:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < jobs[i].size(); j++) {
                  ~~^~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	2036 KB	Output is correct
2	Correct	38 ms	2168 KB	Output is correct
3	Correct	45 ms	2296 KB	Output is correct
4	Correct	44 ms	2296 KB	Output is correct
5	Correct	50 ms	2296 KB	Output is correct
6	Correct	38 ms	2296 KB	Output is correct
7	Correct	36 ms	2296 KB	Output is correct
8	Correct	36 ms	2356 KB	Output is correct
9	Correct	53 ms	4368 KB	Output is correct
10	Correct	43 ms	4448 KB	Output is correct
11	Correct	40 ms	4448 KB	Output is correct
12	Correct	77 ms	4448 KB	Output is correct
13	Correct	133 ms	4780 KB	Output is correct
14	Correct	169 ms	6268 KB	Output is correct
15	Correct	172 ms	6956 KB	Output is correct
16	Correct	272 ms	8876 KB	Output is correct
17	Correct	299 ms	10924 KB	Output is correct
18	Correct	292 ms	10924 KB	Output is correct
19	Correct	448 ms	13740 KB	Output is correct
20	Correct	264 ms	13740 KB	Output is correct