Submission #869821

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869821	2023-11-05T19:02:38 Z	amirhoseinfar1385	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	200 ms	20308 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;
			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;
			continue;
		}
		now++;
		mainres[ret].push_back(all[i].second);
		if(now==mid){
			ret++;
			now=0;
		}
	}
	for(int i=1;i<=n;i++){
		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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	15 ms	2396 KB	Output isn't correct
2	Incorrect	15 ms	2600 KB	Output isn't correct
3	Incorrect	15 ms	2648 KB	Output isn't correct
4	Incorrect	15 ms	2396 KB	Output isn't correct
5	Incorrect	15 ms	2396 KB	Output isn't correct
6	Incorrect	15 ms	2396 KB	Output isn't correct
7	Incorrect	15 ms	2392 KB	Output isn't correct
8	Incorrect	15 ms	2396 KB	Output isn't correct
9	Correct	26 ms	4700 KB	Output is correct
10	Correct	26 ms	4700 KB	Output is correct
11	Correct	21 ms	2140 KB	Output is correct
12	Correct	43 ms	4152 KB	Output is correct
13	Correct	65 ms	6648 KB	Output is correct
14	Correct	95 ms	9228 KB	Output is correct
15	Correct	106 ms	9812 KB	Output is correct
16	Correct	137 ms	12028 KB	Output is correct
17	Correct	164 ms	15912 KB	Output is correct
18	Correct	180 ms	16468 KB	Output is correct
19	Correct	200 ms	20308 KB	Output is correct
20	Correct	162 ms	15912 KB	Output is correct