Submission #869805

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869805	2023-11-05T17:58:39 Z	amirhoseinfar1385	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	211 ms	23124 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;
		}
		if(ret>all[i].first+d){
			return 0;
		}
		now++;
		if(now==mid){
			ret++;
			now=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;
		}
		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	17 ms	2896 KB	Output isn't correct
2	Incorrect	16 ms	2908 KB	Output isn't correct
3	Incorrect	16 ms	2908 KB	Output isn't correct
4	Incorrect	16 ms	2904 KB	Output isn't correct
5	Incorrect	16 ms	2908 KB	Output isn't correct
6	Incorrect	16 ms	2896 KB	Output isn't correct
7	Incorrect	16 ms	2904 KB	Output isn't correct
8	Incorrect	16 ms	2896 KB	Output isn't correct
9	Correct	28 ms	5076 KB	Output is correct
10	Correct	29 ms	4948 KB	Output is correct
11	Correct	23 ms	2644 KB	Output is correct
12	Correct	45 ms	5184 KB	Output is correct
13	Correct	68 ms	7720 KB	Output is correct
14	Correct	99 ms	10624 KB	Output is correct
15	Correct	113 ms	11344 KB	Output is correct
16	Correct	148 ms	14608 KB	Output is correct
17	Correct	169 ms	18904 KB	Output is correct
18	Correct	185 ms	19028 KB	Output is correct
19	Correct	211 ms	23124 KB	Output is correct
20	Correct	175 ms	19028 KB	Output is correct