oj.uz

Submission #77249

# Submission time Handle Problem Language Result Execution time Memory
77249 2018-09-24T11:54:37 Z Vardanyan Job Scheduling (CEOI12_jobs) C++14
90 / 100
 311 ms 33792 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1000 * 100 + 7;
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++){
		int p;
		scanf("%d", &p);
		day[p]++;
		g[p].push_back(i);
	}
	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:29:9: warning: variable 'f' set but not used [-Wunused-but-set-variable]
    bool f = true;
         ^
jobs.cpp:55:8: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   bool f = true;
        ^
jobs.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < as[i].size(); j++){
                   ~~^~~~~~~~~~~~~~
jobs.cpp:12: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", &p);
   ~~~~~^~~~~~~~~~

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7380 KB Output is correct
2 Correct 37 ms 7856 KB Output is correct
3 Correct 36 ms 7984 KB Output is correct
4 Correct 36 ms 8432 KB Output is correct
5 Correct 36 ms 8820 KB Output is correct
6 Correct 55 ms 9128 KB Output is correct
7 Correct 36 ms 9396 KB Output is correct
8 Correct 55 ms 9752 KB Output is correct
9 Correct 46 ms 9872 KB Output is correct
10 Correct 46 ms 10140 KB Output is correct
11 Correct 58 ms 10248 KB Output is correct
12 Correct 67 ms 12616 KB Output is correct
13 Correct 102 ms 16060 KB Output is correct
14 Correct 167 ms 18716 KB Output is correct
15 Correct 176 ms 18716 KB Output is correct
16 Correct 260 ms 21240 KB Output is correct
17 Correct 298 ms 28216 KB Output is correct
18 Correct 287 ms 30204 KB Output is correct
19 Runtime error 311 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 278 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.