Submission #654014

#TimeUsernameProblemLanguageResultExecution timeMemory
654014roimuJob Scheduling (CEOI12_jobs)C++14
100 / 100
462 ms21520 KiB

//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
*/
#Verdict Execution timeMemoryGrader output
Fetching results...