Submission #63346

#	Time	Username	Problem	Language	Result	Execution time	Memory
63346		bazsi700	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	448 ms	13740 KiB

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 (stderr)

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 / 100