Submission #869806

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869806	2023-11-05T17:59:17 Z	amirhoseinfar1385	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	212 ms	20280 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	2536 KB	Output isn't correct
2	Incorrect	16 ms	2396 KB	Output isn't correct
3	Incorrect	16 ms	2396 KB	Output isn't correct
4	Incorrect	19 ms	2564 KB	Output isn't correct
5	Incorrect	16 ms	2396 KB	Output isn't correct
6	Incorrect	16 ms	2532 KB	Output isn't correct
7	Incorrect	16 ms	2392 KB	Output isn't correct
8	Incorrect	17 ms	2392 KB	Output isn't correct
9	Correct	34 ms	4824 KB	Output is correct
10	Correct	27 ms	4840 KB	Output is correct
11	Correct	23 ms	2264 KB	Output is correct
12	Correct	45 ms	4336 KB	Output is correct
13	Correct	68 ms	6600 KB	Output is correct
14	Correct	102 ms	8968 KB	Output is correct
15	Correct	112 ms	9756 KB	Output is correct
16	Correct	145 ms	12056 KB	Output is correct
17	Correct	170 ms	15956 KB	Output is correct
18	Correct	182 ms	16340 KB	Output is correct
19	Correct	212 ms	20280 KB	Output is correct
20	Correct	169 ms	15956 KB	Output is correct