oj.uz

답안 #1117466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1117466 2024-11-23T18:24:02 Z NAMIN Job Scheduling (CEOI12_jobs) C++17
100 / 100
 271 ms 28388 KB 
/*
ID: NAMIN
TASK:
LANG: C++
*/
#include <iostream>
#include <numeric>
#include <math.h>
#include <set>
#include <unordered_set>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <queue>
#include <fstream>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <deque>
#include <assert.h>

#define gcd __gcd
#define endl "\n"
#define ll long long

using namespace std;


void solve(){
	//ifstream cin("milkvisits.in");
	//ofstream cout("milkvisits.out");
	
	int n,d,m;
	cin >> n >> d >> m;
	vector<pair<int,int>> a(m);
	for(int i=0;i<m;i++){
		cin >> a[i].first;
		a[i].second = i;
	}
	
	sort(a.begin(),a.end());

	int ans = 1;
	int l = 1,r = 1e8;
	vector<int> day[n];
	while(l <= r){

		int x = l+(r-l)/2;

		bool ok = true;

		int cur_day = 1,cur_nb = 0;
		vector<int> day_temp[n];
		for(int i=0;i<m;i++){
			if(cur_day-a[i].first < 0){
				cur_day = a[i].first;
				cur_nb = 0;
			}
			else if(cur_nb == x){
				cur_day++;
				cur_nb = 0;
			}

			if(cur_day-a[i].first > d){
				ok = false;
				break;
			}

			cur_nb++;
			day_temp[cur_day-1].push_back(a[i].second+1);
		}

		if(ok && cur_day <= n){
			ans = x;
			r = x-1;
			for(int i=0;i<n;i++){
				day[i] = day_temp[i];
			}
		}
		else
			l = x+1;
	}

	cout << ans << endl;
	for(int i=0;i<n;i++){
		for(int x : day[i]){
			cout << x << ' ';
		}
		cout << "0\n";
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	//cin >> t;
 	while(t--){
		solve();
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 3648 KB Output is correct
2 Correct 38 ms 3640 KB Output is correct
3 Correct 40 ms 3640 KB Output is correct
4 Correct 30 ms 3896 KB Output is correct
5 Correct 32 ms 3800 KB Output is correct
6 Correct 30 ms 3648 KB Output is correct
7 Correct 31 ms 3648 KB Output is correct
8 Correct 38 ms 3648 KB Output is correct
9 Correct 38 ms 8016 KB Output is correct
10 Correct 43 ms 8080 KB Output is correct
11 Correct 34 ms 3400 KB Output is correct
12 Correct 57 ms 6104 KB Output is correct
13 Correct 97 ms 9288 KB Output is correct
14 Correct 142 ms 13344 KB Output is correct
15 Correct 131 ms 14268 KB Output is correct
16 Correct 201 ms 17480 KB Output is correct
17 Correct 234 ms 23112 KB Output is correct
18 Correct 227 ms 23584 KB Output is correct
19 Correct 271 ms 28388 KB Output is correct
20 Correct 239 ms 23112 KB Output is correct