Submission #99884

#	Time	Username	Problem	Language	Result	Execution time	Memory
99884		bharat2002	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	411 ms	17528 KiB

jobs

/*input
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e6 + 100;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
pii arr[N];int n, m, d, oriarr[N];//vector<int> days[N];
bool final;
bool p(int x){
	int ptr=1;
	for(int i=1;i<=n;i++)
	{
		int ct=0;
		while(ptr<=m&&arr[ptr].f<=i&&ct<x) 
		{
			if(arr[ptr].f+d>=i) ptr++;
			else return false;
			if(final) cout<<arr[ptr-1].s<<" ";
			ct++;
		}
		if(final) cout<<0<<endl;
	}
	if(ptr<=m) return false;
	return true;
}
bool sf(pii a, pii b){
	return a.f<b.f;
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>d>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>arr[i].f;arr[i].s=i;oriarr[i]=arr[i].f;
	}
	sort(arr+1, arr+m+1, sf);
	int low=1, high=m;
	final=0;
	while(low<high)
	{
		int mid=(low+high)/2;
		if(p(mid)) high=mid;
		else low=mid+1;
	}
	final=1;
	cout<<low<<endl;
	p(low);
}

• Subtask 1: 100 / 100