Submission #906650

#	Time	Username	Problem	Language	Result	Execution time	Memory
906650		damamila	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	230 ms	42948 KiB

jobs

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long

signed main() {
	int n, d, m;
	cin >> n >> d >> m;
	vector<vector<int>> req(n-d);
	for (int i = 1; i <= m; i++) {
		int a;
		cin >> a;
		a--;
		req[a].push_back(i);
	}
	int l = 0, r = m;
	int mi;
	while (l < r) {
		mi = (l+r)/2;
		//cout << mi << endl;
		bool w = 1;
		int i = 0;
		int j = 0;
		int day = 0;
		int hr = 0; //wie viele requests schon gemacht wurden am tag
		while (i < n-d) {
			if (hr == mi) {
				day++;
				hr = 0;
			}
			if (j >= req[i].size()) { //falls nichts mehr gibt vom tag
				i++;
				j = 0;
				if (i > day) {
					day++;
				}
			}
			if (i < n-d) {
				//mach naechsten request
				//cout << day << ": " << i << " " << j << " " << req[i][j] << endl;
				if (day > i+d) { //zu spaet gemacht
					w = 0;
				}
				hr++;
				j++;
			}
		}
		if (w) {
			r = mi;
		} else {
			l = mi+1;
		}
	}
	cout << mi << endl;
	int i = 0;
	int j = 0;
	int day = 0;
	int hr = 0; //wie viele requests schon gemacht wurden am tag
	vector<vector<int>> ans;
	ans.push_back({});
	while (i < n-d) {
		if (hr == mi) {
			day++;
			hr = 0;
				ans[ans.size()-1].push_back(0);
				ans.push_back({});
		}
		if (j >= req[i].size()) { //falls nichts mehr gibt vom tag
			i++;
			j = 0;
			if (i > day) {
				day++;
				ans[ans.size()-1].push_back(0);
				ans.push_back({});
			}
		}
		if (i < n-d) {
			//mach naechsten request
			ans[ans.size()-1].push_back(req[i][j]);
			hr++;
			j++;
		}
	}
	ans[ans.size()-1].push_back(0);
	for (auto i : ans) {
		for (int j : i) {
			cout << j << " ";
		}
		cout << endl;
	}
	cout << 0 << endl;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:33:10: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |    if (j >= req[i].size()) { //falls nichts mehr gibt vom tag
      |        ~~^~~~~~~~~~~~~~~~
jobs.cpp:70:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   if (j >= req[i].size()) { //falls nichts mehr gibt vom tag
      |       ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100