Submission #602611

#TimeUsernameProblemLanguageResultExecution timeMemory
602611hailJob Scheduling (CEOI12_jobs)C++17
50 / 100
667 ms16968 KiB

#include <bits/stdc++.h>

using namespace std;

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;
			if(dr==0)
			{
				day++;
				dr=mach;
			}
			continue;
		}
		day += s/mach;
		dr = mach - (s%mach);
		if(dr == 0) {day++; dr = 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 = 1000001;
	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";
	}

}
#Verdict Execution timeMemoryGrader output
Fetching results...