oj.uz

Submission #77248

# Submission time Handle Problem Language Result Execution time Memory
77248 2018-09-24T11:53:09 Z Vardanyan Job Scheduling (CEOI12_jobs) C++14
80 / 100
 392 ms 33792 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1000 * 100 + 7;
int a[N*10];
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];
			printf("%d ", e);
			g[l].pop_back();
		}
		printf("%d\n", 0);
	}
	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
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7756 KB Output is correct
2 Correct 40 ms 8328 KB Output is correct
3 Correct 45 ms 8548 KB Output is correct
4 Correct 40 ms 8796 KB Output is correct
5 Correct 41 ms 9316 KB Output is correct
6 Correct 41 ms 9552 KB Output is correct
7 Correct 39 ms 9816 KB Output is correct
8 Correct 39 ms 10140 KB Output is correct
9 Correct 55 ms 10316 KB Output is correct
10 Correct 59 ms 10584 KB Output is correct
11 Correct 44 ms 10696 KB Output is correct
12 Correct 85 ms 13452 KB Output is correct
13 Correct 127 ms 17872 KB Output is correct
14 Correct 209 ms 22736 KB Output is correct
15 Correct 205 ms 24396 KB Output is correct
16 Correct 311 ms 30784 KB Output is correct
17 Runtime error 361 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
18 Runtime error 349 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
19 Runtime error 392 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
20 Runtime error 376 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.