제출 #563659

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
563659		israeladewuyi	Job Scheduling (CEOI12_jobs)	C++17	75 / 100	603 ms	48844 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;

pair<bool, vector<vector<int>>> bin_search(int mid,  vector<pair<int, int>> &A){
	vector<vector<int>>B(N);

	int idx = 0;

	for(int day = 1; day <= N; day++){
		for(int j = 0; j < mid; j++){
			if(A[idx].first > day){
				break;
			}

			if(A[idx].first + D >= day){
				B[day - 1].push_back(A[idx].second);
				idx++;
			}
			else return {false, B};

			if(idx == M){
				return {true, B};
			}
		}
	}
	return {false, B};
}


int32_t main(){
	// freopen("angry.in", "r", stdin);
	// freopen("angry.out", "w", stdout);
	
	cin>>N>>D>>M;

	vector<pair<int, int>>A;
	
	for(int i = 0; i < M; i++){
		cin>>a;
		A.push_back({a, i + 1});
	}

	sort(A.begin(), A.end());

	vector<vector<int>>res;
	int left = 0, right = M;

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

		pair<bool, vector<vector<int>>> answer = bin_search(mid, A);
		
		if(answer.first == true){
			right = mid;
			res = answer.second;
		}
		else left = mid + 1;
	}

	cout<<right<<endl;

	for(int i = 0; i < N; i++){
		for(auto &a : res[i])cout<<a<<" ";
		cout<<0<<endl;
	}

	

	return 0;
}

• Subtask 1: 75 / 100