oj.uz

Submission #654014

# Submission time Handle Problem Language Result Execution time Memory
654014 2022-10-29T11:15:02 Z roimu Job Scheduling (CEOI12_jobs) C++14
100 / 100
 462 ms 21520 KB 
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

typedef long long LL;
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

LL n, d, m;

bool f(LL mid,const vector<pair<LL,LL>>& jobs,const vector<LL>& rui) {
	LL p = 0;
	for (int i = 1; i <= n; i++) {
		if (jobs[p].first > i)continue;
		if ((jobs[p].first+d)<i)return false;
		

		p = min(p + mid, rui[i]);
		if (p == m)return true;
	}
	if (p == m)return true;
	return false;
}

int main() {
	 cin >> n >> d >> m;

	vector<pair<LL, LL>> jobs;
	for (int i = 0; i < m; i++) {
		LL x; cin >> x;
		jobs.push_back({ x,i + 1 });
	}

	sort(jobs.begin(), jobs.end());
	vector<LL> rui(n + 2);
	LL nowd = 1;
	for (int i = 0; i < m; i++) {
		if (nowd == jobs[i].first) {
			rui[nowd]++;
		}
		else if (nowd < jobs[i].first) {
			LL x = rui[nowd];
			while (nowd < jobs[i].first) {
				rui[nowd++] = x;
			}
			rui[nowd] = x + 1;
		}
	}
	
	LL val = *max_element(rui.begin(), rui.end());;
	while (nowd < n+2) {
		rui[nowd++] = val;
	}

	
	

	//機械の数を決め打ち、多いほうが達成しやすい
	LL ng = 0; LL ok = 1000100;
	while (abs(ng - ok) > 1) {
		LL mid = min(ng, ok) + abs(ng - ok) / 2;
		if (f(mid,jobs,rui)) {
			ok = mid;
		}
		else {
			ng = mid;
		}
	}

	cout << ok << endl;
	LL p = 0;
	for (int i = 1; i <= n; i++) {
		LL cnt = ok;
		while (p<m&&jobs[p].first<= i) {
			
			cout << jobs[p].second <<" ";
			p++;
			cnt--;
			if (cnt == 0) {
				break;
			}
			
		}cout << 0 << endl;
	}
	return 0;
}

/*
5 1 3
2 2 2
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2516 KB Output is correct
2 Correct 44 ms 2508 KB Output is correct
3 Correct 44 ms 2500 KB Output is correct
4 Correct 41 ms 2488 KB Output is correct
5 Correct 39 ms 2492 KB Output is correct
6 Correct 40 ms 2484 KB Output is correct
7 Correct 39 ms 2500 KB Output is correct
8 Correct 45 ms 2616 KB Output is correct
9 Correct 189 ms 3528 KB Output is correct
10 Correct 149 ms 3404 KB Output is correct
11 Correct 39 ms 2492 KB Output is correct
12 Correct 81 ms 4840 KB Output is correct
13 Correct 150 ms 8660 KB Output is correct
14 Correct 176 ms 9280 KB Output is correct
15 Correct 206 ms 11556 KB Output is correct
16 Correct 297 ms 16872 KB Output is correct
17 Correct 299 ms 16804 KB Output is correct
18 Correct 323 ms 18444 KB Output is correct
19 Correct 462 ms 21520 KB Output is correct
20 Correct 346 ms 16804 KB Output is correct