Submission #869823

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869823	2023-11-05T19:06:25 Z	amirhoseinfar1385	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	213 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;
		}
	}
	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++){
		if((int)mainres[i].size()>mid){
			assert(0);
		}
		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	2652 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	15 ms	2396 KB	Output isn't correct
5	Incorrect	15 ms	2532 KB	Output isn't correct
6	Incorrect	15 ms	2392 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	25 ms	4700 KB	Output is correct
10	Correct	26 ms	4828 KB	Output is correct
11	Correct	22 ms	2144 KB	Output is correct
12	Correct	44 ms	4176 KB	Output is correct
13	Correct	65 ms	6736 KB	Output is correct
14	Correct	93 ms	9044 KB	Output is correct
15	Correct	108 ms	9732 KB	Output is correct
16	Correct	147 ms	12048 KB	Output is correct
17	Correct	164 ms	15908 KB	Output is correct
18	Correct	181 ms	16560 KB	Output is correct
19	Correct	213 ms	20048 KB	Output is correct
20	Correct	173 ms	15916 KB	Output is correct