Submission #1166140

#TimeUsernameProblemLanguageResultExecution timeMemory
1166140beheshtJob Scheduling (CEOI12_jobs)C++20
100 / 100
171 ms13884 KiB
#include <bits/stdc++.h>

#define ld                   long double
#define ll                   long long
#define pb                   push_back
#define mk                   make_pair
#define S                    second
#define Y                    second
#define F                    first 
#define X                    first
#define arr(x)               array <int, x>
#define debug(x)             cout << #x << " : " << x << endl << flush
#define _debug(x, y, z)      cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define __debug(x, y, z, a)  cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define endl                 '\n'

using namespace std;

const int INF = 1e9 + 24 + (11/10);
const int MAXN = 1e6 + 24 + (11/10);

arr(2) a[MAXN];

signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, d, m;
	cin >> n >> d >> m;
	
	for(int i = 0; i < m; i++){
		cin >> a[i][0];
		a[i][1] = i;
	}
	
	sort(a, a + m);
	
	int l = 0, r = m, mid;
	
	while(r - l > 1){
		mid = (r + l) >> 1;
		
		int cnt = 0;
		int day = 1;
		bool flag = 1;
		
		for(int i = 0; i < m; i++){
			
			int x = a[i][0];
			
			if(x > day){
				day = x;
				cnt = 1;
				
				if(mid == cnt){
					cnt = 0;
					day++;
				}
			}
			
			else if(cnt == mid){
				cnt = 1;
				day++;
				
				if(day - a[i][0] > d)
					flag = 0;
			}
			
			else{
				if(day - a[i][0] > d)
					flag = 0;
				cnt++;
			} 
		}
		
		if(day <= n && flag)
			r = mid;
		
		else 
			l = mid;
	}
	
	int day = 1;
	int cnt = 0;
	
	cout << r << endl;
	
	for(int i = 0; i < m; i++){
		
		int x = a[i][0];
		int ind = a[i][1] + 1;
		
		if(x > day){
			for(int i = 0; i < x - day; i++)
				cout << 0 << endl;
			
			day = x;
			cnt = 1;
		}
		
		else if(cnt == r){
			cnt = 1;
			day++;
			cout << 0 << endl;
		}
		
		else
			cnt++;
			
		cout << ind << " ";
	}
	
	
	for(int i = 0; i < n - day + 1; i++)
		cout << 0 << endl;
}

// Man hamooonam ke ye rooz...
#Verdict Execution timeMemoryGrader output
Fetching results...