oj.uz

Submission #99884

# Submission time Handle Problem Language Result Execution time Memory
99884 2019-03-08T10:46:38 Z bharat2002 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 411 ms 17528 KB 
/*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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2176 KB Output is correct
2 Correct 38 ms 2168 KB Output is correct
3 Correct 36 ms 2168 KB Output is correct
4 Correct 40 ms 2168 KB Output is correct
5 Correct 34 ms 2296 KB Output is correct
6 Correct 50 ms 2168 KB Output is correct
7 Correct 36 ms 2176 KB Output is correct
8 Correct 36 ms 2176 KB Output is correct
9 Correct 162 ms 2424 KB Output is correct
10 Correct 164 ms 2424 KB Output is correct
11 Correct 31 ms 2168 KB Output is correct
12 Correct 55 ms 3960 KB Output is correct
13 Correct 90 ms 6008 KB Output is correct
14 Correct 130 ms 8056 KB Output is correct
15 Correct 139 ms 9976 KB Output is correct
16 Correct 206 ms 11768 KB Output is correct
17 Correct 243 ms 13560 KB Output is correct
18 Correct 267 ms 15608 KB Output is correct
19 Correct 411 ms 17528 KB Output is correct
20 Correct 252 ms 13688 KB Output is correct