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
#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);
}
# 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