Submission #563463

#	Time	Username	Problem	Language	Result	Execution time	Memory
563463		israeladewuyi	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	883 ms	61484 KiB

jobs

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

#define int ll
#define endl "\n"

long long a,b,c,d,e,f,m,n,h,l,r,k,x,y,ans,sum;

// bool sortcol(const vector<int>& v1, const vector<int>& v2){
//     return v1[1] < v2[1];
// }

int C, D, K, N, M;
vector<vector<int>>A(1000005, vector<int>(2));
bool bin_search(int mid){
	int limit = A[0][0] + D;
	int count = 0;
	int day_count = 1;

	for(int i = 0; i < M;i++){
		if(day_count > A[i][0]){
			return false;
		}

		if(A[i][0] <= limit and count < mid){
			count++;
		}
		else{
			++day_count;
			limit = A[i][0] + D;
			count = 0;
			if(A[i][0] <= limit and count < mid){
				count++;
			}
		}
		// cout<<A[i][0]<<" "<<day_count<<" "<<count<<" "<<mid<<endl;
	}
	// cout<<day_count<<" "<<mid<<endl;
	return day_count <= N;
}


int32_t main(){
	// freopen("angry.in", "r", stdin);
	// freopen("angry.out", "w", stdout);
	
	cin>>N>>D>>M;
	
	for(int i = 0; i < M; i++){
		cin>>a;
		A[i][0] = a;
		A[i][1] = i + 1;
	}

	sort(A.begin(), A.begin() + M);

	// for(int i = 0; i < M; i++){
	// 	cout<<A[i][0]<<" "<<A[i][1]<<endl;
	// }

	int left = 0, right = M;

	while(left < right){
		int mid = left + ((right - left) / 2);

		if(bin_search(mid)){
			right = mid;
		}
		else left = mid + 1;
	}

	cout<<right;
	int k = 0;
	for(int i = 0; i < N; i++){
		int j = right;
		while(k < M and j--){
			cout<<A[k][1]<<" ";
			k++;
		}
		cout<<0<<endl;
	}

	return 0;
}

• Subtask 1: 0 / 100