oj.uz

Submission #906650

# Submission time Handle Problem Language Result Execution time Memory
906650 2024-01-14T16:14:43 Z damamila Job Scheduling (CEOI12_jobs) C++14
0 / 100
 230 ms 42948 KB 
// 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

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

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 3020 KB Execution killed with signal 11
2 Runtime error 18 ms 3008 KB Execution killed with signal 11
3 Runtime error 19 ms 3024 KB Execution killed with signal 11
4 Runtime error 18 ms 3020 KB Execution killed with signal 11
5 Runtime error 18 ms 3024 KB Execution killed with signal 11
6 Runtime error 18 ms 3044 KB Execution killed with signal 11
7 Runtime error 17 ms 3024 KB Execution killed with signal 11
8 Runtime error 18 ms 3116 KB Execution killed with signal 11
9 Runtime error 25 ms 9556 KB Execution killed with signal 11
10 Runtime error 24 ms 9820 KB Execution killed with signal 11
11 Incorrect 27 ms 3472 KB Output isn't correct
12 Incorrect 49 ms 6484 KB Expected EOLN
13 Incorrect 77 ms 11892 KB Expected EOLN
14 Incorrect 135 ms 15632 KB Expected EOLN
15 Incorrect 128 ms 18952 KB Output isn't correct
16 Incorrect 190 ms 19820 KB Expected EOLN
17 Incorrect 227 ms 29068 KB Expected EOLN
18 Runtime error 176 ms 38480 KB Execution killed with signal 11
19 Runtime error 188 ms 42948 KB Execution killed with signal 11
20 Incorrect 230 ms 29104 KB Expected EOLN