Submission #869824

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869824	2023-11-05T19:07:28 Z	amirhoseinfar1385	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	236 ms	20052 KB

jobs

#include<bits/stdc++.h>
using namespace std;
int n,d,m;
vector<pair<int,int>>all;

bool check(int mid){
	int ret=1,now=0;
	for(int i=0;i<m;i++){
		if(all[i].first>ret){
			ret++;
			now=0;
			i--;
			continue;
		}
		if(ret>all[i].first+d){
			return 0;
		}
		now++;
		if(now==mid){
			ret++;
			now=0;
		}
	}
	if(now==0){
		ret--;
	}
	if(ret>n){
		return 0;
	}
	return 1;
}

void co(int mid){
	int ret=1,now=0;
	vector<vector<int>>mainres(n+1);
	for(int i=0;i<m;i++){
		if(all[i].first>ret){
			ret++;
			now=0;
			i--;
			continue;
		}
		now++;
		mainres[ret].push_back(all[i].second);
		if(now==mid){
			ret++;
			now=0;
		}
	}
	for(int i=1;i<=n;i++){
		if((int)mainres[i].size()>mid){
			assert(0);
		}
		for(auto x:mainres[i]){
			cout<<x+1<<" ";
		}
		cout<<0<<"\n";
	}
}

long long solve(){
	long long low=0,high=1e9+5,mid;
	while(high-low>1){
		mid=(high+low)>>1;
		if(check(mid)){
			high=mid;
		}
		else{
			low=mid;
		}
	}
	return high;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>d>>m;
	all.resize(m);
	for(int i=0;i<m;i++){
		cin>>all[i].first;
		all[i].second=i;
	}
	sort(all.begin(),all.end());
	int res=solve();
	cout<<res<<"\n";
	co(res);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	2392 KB	Output is correct
2	Correct	16 ms	2396 KB	Output is correct
3	Correct	16 ms	2396 KB	Output is correct
4	Correct	23 ms	2652 KB	Output is correct
5	Correct	16 ms	2392 KB	Output is correct
6	Correct	24 ms	2396 KB	Output is correct
7	Correct	21 ms	2396 KB	Output is correct
8	Correct	16 ms	2396 KB	Output is correct
9	Correct	26 ms	4692 KB	Output is correct
10	Correct	26 ms	4700 KB	Output is correct
11	Correct	22 ms	2136 KB	Output is correct
12	Correct	45 ms	4180 KB	Output is correct
13	Correct	67 ms	6632 KB	Output is correct
14	Correct	95 ms	9044 KB	Output is correct
15	Correct	118 ms	9728 KB	Output is correct
16	Correct	141 ms	12112 KB	Output is correct
17	Correct	168 ms	15848 KB	Output is correct
18	Correct	192 ms	16436 KB	Output is correct
19	Correct	236 ms	20052 KB	Output is correct
20	Correct	170 ms	15908 KB	Output is correct