Submission #772286

#	Time	Username	Problem	Language	Result	Execution time	Memory
772286		1ne	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	137 ms	16952 KiB

jobs

/*
*  author : Apiram                  
*  created: 04.07.2023 03:13:11
*/

#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m,d;cin>>n>>d>>m;        
	vector<vector<int>>adj(n);
	for (int i = 0;i<m;++i){
		int x;cin>>x;
		adj[x - 1].push_back(i);
	}
	int left = 0,right = m;
	int pos = -1;
	while(left<=right){
		int mid = (left + right)>>1;
		queue<int>q;
		bool ok = true;
		for (int i = 0;i<n;++i){
			for (auto x:adj[i]){
				q.push(i);
			}
	 		for (int j = 0;j<mid && !q.empty();++j){
	 			if (i - q.front() > d){
	 				ok = false;
	 				break;
	 			}
	 			q.pop();
	 		}
	 		if (!ok)break;
		}
		if (!q.empty())ok = false;
		if (ok){
			right = mid - 1;
			pos = mid;
		}
		else left = mid + 1;
	}
	cout<<pos<<'\n';
	queue<int>q;
	for (int i = 0;i<n;++i){
		for (auto x:adj[i]){
			q.push(x + 1);
		}
		for (int j = 0;j<pos && !q.empty();++j){
			cout<<q.front()<<" ";
			q.pop();
		}
		cout<<0<<'\n';
	}
	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:25:14: warning: unused variable 'x' [-Wunused-variable]
   25 |    for (auto x:adj[i]){
      |              ^

• Subtask 1: 100 / 100