oj.uz

Submission #772286

# Submission time Handle Problem Language Result Execution time Memory
772286 2023-07-03T21:57:06 Z 1ne Job Scheduling (CEOI12_jobs) C++14
100 / 100
 137 ms 16952 KB 
/*
*  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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2288 KB Output is correct
2 Correct 15 ms 2260 KB Output is correct
3 Correct 14 ms 2192 KB Output is correct
4 Correct 15 ms 2248 KB Output is correct
5 Correct 14 ms 2260 KB Output is correct
6 Correct 19 ms 2160 KB Output is correct
7 Correct 14 ms 2200 KB Output is correct
8 Correct 15 ms 2180 KB Output is correct
9 Correct 23 ms 4384 KB Output is correct
10 Correct 21 ms 4300 KB Output is correct
11 Correct 15 ms 1876 KB Output is correct
12 Correct 30 ms 3344 KB Output is correct
13 Correct 44 ms 5704 KB Output is correct
14 Correct 78 ms 8220 KB Output is correct
15 Correct 72 ms 8624 KB Output is correct
16 Correct 102 ms 11460 KB Output is correct
17 Correct 120 ms 13796 KB Output is correct
18 Correct 117 ms 13624 KB Output is correct
19 Correct 137 ms 16952 KB Output is correct
20 Correct 119 ms 13828 KB Output is correct