Submission #869810

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869810	2023-11-05T18:02:47 Z	amirhoseinfar1385	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	202 ms	20048 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;
		}
	}
	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	2392 KB	Output isn't correct
3	Incorrect	15 ms	2396 KB	Output isn't correct
4	Incorrect	16 ms	2392 KB	Output isn't correct
5	Incorrect	15 ms	2396 KB	Output isn't correct
6	Incorrect	18 ms	2396 KB	Output isn't correct
7	Incorrect	15 ms	2396 KB	Output isn't correct
8	Incorrect	15 ms	2396 KB	Output isn't correct
9	Correct	26 ms	4836 KB	Output is correct
10	Correct	27 ms	4720 KB	Output is correct
11	Correct	24 ms	2320 KB	Output is correct
12	Correct	44 ms	4180 KB	Output is correct
13	Correct	69 ms	6744 KB	Output is correct
14	Correct	95 ms	8952 KB	Output is correct
15	Correct	109 ms	9808 KB	Output is correct
16	Correct	147 ms	12116 KB	Output is correct
17	Correct	163 ms	15920 KB	Output is correct
18	Correct	177 ms	16432 KB	Output is correct
19	Correct	202 ms	20048 KB	Output is correct
20	Correct	162 ms	15912 KB	Output is correct