oj.uz

Submission #77247

# Submission time Handle Problem Language Result Execution time Memory
77247 2018-09-24T11:51:25 Z Vardanyan Job Scheduling (CEOI12_jobs) C++14
0 / 100
 47 ms 33792 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1000 * 1000 + 7;
int a[N];
int day[N];
vector<int> g[N];
vector<int> as[N];
int main(){
	int n, d, m;
	scanf("%d%d%d", &n, &d, &m);
	for (int i = 1; i <= m; i++){
		scanf("%d", &a[i]);
		day[a[i]]++;
		g[a[i]].push_back(i);
	}
	sort(a + 1, a + 1 + m);
	int l = 1;
	int r = m;
	int ans = m;
	
	while (l <= r){
		int mid = (l + r) / 2;
		queue<int> q;
		for (int i = 1; i <= n; i++){
			int x = day[i];
			while (x--) q.push(i);
			bool f = true;
			int num = mid;
			while (!q.empty()){
				int v = q.front();
				if (i > v + d){
					f = false;
					break;
				}
				if (num > 0){
					q.pop();
					num--;
				}
				else break;
			}
		}
		if (q.empty()) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	int mid = ans;
	queue<int> q;
	for (int i = 1; i <= n; i++){
		int x = day[i];
		while (x--) q.push(i);
		bool f = true;
		int num = mid;
		while (!q.empty()){
			int v = q.front();
			if (i > v + d){
				f = false;
				break;
			}
			if (num > 0){
				q.pop();
				num--;
				as[i].push_back(v);
			}
			else break;
		}
	}
	cout << ans << endl;
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < as[i].size(); j++){
			int l = as[i][j];
			int e = g[l][g[l].size() - 1];
			cout << e << " ";
			g[l].pop_back();
		}
		cout << 0 << endl;
	}
	return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:30:9: warning: variable 'f' set but not used [-Wunused-but-set-variable]
    bool f = true;
         ^
jobs.cpp:56:8: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   bool f = true;
        ^
jobs.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < as[i].size(); j++){
                   ~~^~~~~~~~~~~~~~
jobs.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &d, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 39 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 39 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 38 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 36 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 47 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 38 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 40 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 35 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 37 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 41 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 38 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 37 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 38 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 40 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 36 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 40 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 39 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 38 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 38 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)