제출 #602446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602446		hail	Job Scheduling (CEOI12_jobs)	C++17	50 / 100	731 ms	14388 KiB

jobs

#include <bits/stdc++.h>

using namespace std;


#define mp make_pair

int n, d, m;

vector<vector<int>> jobs(1, vector<int>(0));

bool check(int mach)
{
	int day=1;
	int dr=mach;

	int s;
	for(int i=1 ; i<=n; i++)
	{
		s = (int)jobs[i].size();
		if(day<i) {day=i; dr=mach;}
		if(s>dr) {s-=dr; day++; dr=mach;}
		else { dr-=s; s = 0; continue;}
		if(dr==0) {day++; dr=mach;}
		day += s/mach;
		dr = mach - (s%mach);
		if(day>i+d || day>n) return false;
	}
	return true;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	
	cin>>n>>d>>m;

	jobs.resize(n+1);
	int o;

	for(int i=1; i<=m; i++)
	{
		cin>>o;
		jobs[o].push_back(i);
	}

	int high = 100000001;
	int low = 0;
	int mid;
	while(high-low>1)
	{
		mid = (high+low)/2;
		if(check(mid)) high = mid;
		else low = mid;
	}

	cout<<high<<"\n";

	int num_mach = high;
	int curr=1;
	int cnt=0;
	for(int i = 1; i<=n ; i++)
	{
		cnt = 0;
		while((cnt<num_mach))
		{
			if(jobs[curr].empty())
			{
				while((jobs[curr].empty()))
				{
					curr++;
					if(curr>i) break;
				}
				if(curr>i || curr>n-d)
				{
					cout<<0<<"\n";
					cnt=0;
					break;
				}
			}
			cout<<jobs[curr][0]<<" ";
			jobs[curr].erase(jobs[curr].begin());
			cnt++;
		}
		if(cnt==num_mach) cout<<0<<"\n";
	}

}

• Subtask 1: 50 / 100