oj.uz

Submission #744287

# Submission time Handle Problem Language Result Execution time Memory
744287 2023-05-18T10:25:37 Z MODDI Job Scheduling (CEOI12_jobs) C++14
10 / 100
 516 ms 23900 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, d, m;
vector<pii> arr;
bool check(int machines){
	int job = m-1;
	for(int day = n; day >= 1; day--){
		int cnt = 0;
		while(arr[job].first - day <= d && cnt + 1 <= machines){
			job--;
			cnt++;
		}
		if(job < 0)	return true;
	}
	return false;
}
int main(){
	cin>>n>>d>>m;
	arr.resize(m);
	for(int i = 0; i < m; i++)
	{
		cin>>arr[i].first;
		arr[i].second = i+1;
	}
	sort(arr.begin(), arr.end());
	int l = 1, r = 1e6+10, ans = -1;
	while(l <= r){
		int mid = (l + r) / 2;
		bool can = check(mid);
		if(can){
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
//	cout<<ans<<endl;
	vi each_day[n+1];
	int job = m-1;
	for(int day = n; day >= 1; day--){
		int cnt = 0;
		while(job >= 0 && arr[job].first - day <= d && cnt + 1 <= ans){
			each_day[day].pb(arr[job].second);
			job--;
			cnt++;
		}
	}
	cout<<ans<<endl;
	for(int day = 1; day <= n; day++){
		for(auto t : each_day[day])
			cout<<t<<" ";
		cout<<0<<endl;
	}
	return 0;
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 2564 KB Output isn't correct
2 Incorrect 46 ms 2560 KB Output isn't correct
3 Incorrect 42 ms 2584 KB Output isn't correct
4 Incorrect 42 ms 2588 KB Output isn't correct
5 Incorrect 46 ms 2508 KB Output isn't correct
6 Incorrect 43 ms 2508 KB Output isn't correct
7 Incorrect 41 ms 2584 KB Output isn't correct
8 Incorrect 42 ms 2616 KB Output isn't correct
9 Incorrect 167 ms 7284 KB Output isn't correct
10 Incorrect 159 ms 7244 KB Output isn't correct
11 Incorrect 44 ms 2128 KB Output isn't correct
12 Correct 82 ms 4156 KB Output is correct
13 Incorrect 120 ms 6556 KB Output isn't correct
14 Correct 185 ms 9036 KB Output is correct
15 Incorrect 199 ms 9596 KB Output isn't correct
16 Incorrect 271 ms 11896 KB Output isn't correct
17 Incorrect 314 ms 15980 KB Output isn't correct
18 Incorrect 327 ms 17464 KB Output isn't correct
19 Incorrect 516 ms 23900 KB Output isn't correct
20 Incorrect 321 ms 16012 KB Output isn't correct