Submission #602408

#	Time	Username	Problem	Language	Result	Execution time	Memory
602408		hail	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	42 ms	65536 KiB

jobs

#include <bits/stdc++.h>

using namespace std;


#define mp make_pair

int n, d, m;

queue<int> jobs[100001]{};

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;

	int o;

	for(int i=1; i<=m; i++)
	{
		cin>>o;
		jobs[o].push(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<=i)
				{
					curr++;
				}
				if(curr>i)
				{
					cout<<0<<"\n";
					cnt=0;
					break;
				}
			}
			cout<<jobs[curr].front()<<" ";
			jobs[curr].pop();
			cnt++;
		}
		if(cnt==num_mach) cout<<0<<"\n";
	}

}

• Subtask 1: 0 / 100