oj.uz

Submission #77250

# Submission time Handle Problem Language Result Execution time Memory
77250 2018-09-24T11:59:35 Z Abelyan Job Scheduling (CEOI12_jobs) C++17
25 / 100
 309 ms 33792 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;

#define N 1000006
#define fr first
#define sc second

pair<int,int> a[N];
int n, m, d;
vector<int> days[N];
bool solve(int k){
	queue<int> q;
	int day = 1;
	for (int i = 0; i < m; day++){
		days[day].clear();
		int tv = a[i].fr;
		while (a[i].fr == tv){
			q.push(i);
			i++;
		}
		for (int j = 0; j < k && !q.empty(); j++){
			if (a[q.front()].fr + d < day) return false;
			days[day].push_back(a[q.front()].sc);
			q.pop();
		}
	}
	while (day <= n){
		days[day].clear();
		for (int j = 0; j < k && !q.empty(); j++){
			if (a[q.front()].fr + d  < day) return false;
			days[day].push_back(a[q.front()].sc);
			q.pop();
		}
		day++;
	}
	if (q.size()) return false;
	return true;
}

int main(){
	ios_base::sync_with_stdio(false);
	
	cin >> n >> d >> m;
	for (int i = 0; i < m; i++){
		cin >> a[i].fr;
		a[i].sc = i;
	}
	sort(a, a + m);
	int l = 0,r=m;
	while (l < r){
		//cout << l << " " << r << endl;
		int tm = (l + r) / 2;
		if (solve(tm))r = tm;
		else l = tm + 1;
	}
	solve(l);
	cout << l << endl;
	for (int i = 0; i < n; i++){
		for (auto tv : days[i + 1]){
			cout << tv+1 << " ";
		}
		cout << 0 << endl;
	}
	system("pause");
	return 0;
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:68:8: warning: ignoring return value of 'int system(const char*)', declared with attribute warn_unused_result [-Wunused-result]
  system("pause");
  ~~~~~~^~~~~~~~~

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 26968 KB Output isn't correct
2 Incorrect 72 ms 27212 KB Output isn't correct
3 Incorrect 69 ms 27212 KB Output isn't correct
4 Incorrect 74 ms 27240 KB Output isn't correct
5 Incorrect 70 ms 27440 KB Output isn't correct
6 Incorrect 70 ms 27588 KB Output isn't correct
7 Incorrect 72 ms 27588 KB Output isn't correct
8 Incorrect 70 ms 27648 KB Output isn't correct
9 Correct 227 ms 27648 KB Output is correct
10 Correct 216 ms 27648 KB Output is correct
11 Correct 67 ms 27648 KB Output is correct
12 Correct 109 ms 28172 KB Output is correct
13 Correct 148 ms 30592 KB Output is correct
14 Runtime error 216 ms 33660 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.
15 Runtime error 233 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.
16 Runtime error 309 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.
17 Runtime error 199 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 214 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 231 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 191 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)