Submission #869822

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869822	2023-11-05T19:04:27 Z	amirhoseinfar1385	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	210 ms	20284 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;
		if(all[i].first==0){
			assert(0);
		}
		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	19 ms	2392 KB	Output isn't correct
2	Incorrect	15 ms	2396 KB	Output isn't correct
3	Incorrect	15 ms	2396 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	16 ms	2568 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	30 ms	4696 KB	Output is correct
10	Correct	28 ms	4688 KB	Output is correct
11	Correct	22 ms	2140 KB	Output is correct
12	Correct	45 ms	4180 KB	Output is correct
13	Correct	67 ms	6628 KB	Output is correct
14	Correct	93 ms	9160 KB	Output is correct
15	Correct	108 ms	9808 KB	Output is correct
16	Correct	141 ms	12056 KB	Output is correct
17	Correct	164 ms	15912 KB	Output is correct
18	Correct	184 ms	16532 KB	Output is correct
19	Correct	210 ms	20284 KB	Output is correct
20	Correct	164 ms	15952 KB	Output is correct