Submission #77250

#	Time	Username	Problem	Language	Result	Execution time	Memory
77250		Abelyan	Job Scheduling (CEOI12_jobs)	C++17	25 / 100	309 ms	33792 KiB

jobs

#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 (stderr)

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 / 100