Submission #654010

#	Time	Username	Problem	Language	Result	Execution time	Memory
654010		roimu	Job Scheduling (CEOI12_jobs)	C++14	40 / 100	479 ms	21556 KiB

jobs

//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) {
	int p = 0;
	for (int i = 1; i <= n; i++) {
		if (jobs[p].first>(i+d))return false;
		if (jobs[p].first > i)continue;

		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 + 1);
	int 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 = rui[nowd];
	while (nowd < n+1) {
		rui[nowd++] = val;
	}

	
	

	//機械の数を決め打ち、多いほうが達成しやすい
	LL ng = 0; LL ok = 1000010;
	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;
	int p = 0;
	for (int i = 1; i <= n; i++) {
		int cnt = ok;
		while (p<m&&jobs[p].first<= i) {
			
			cout << jobs[p].second <<" ";
			p++;
			cnt--;
			if (cnt == 0) {
				break;
			}
			
		}cout << 0 << endl;
	}
	return 0;
}

/*
10 10 9
1 2 2 4 6 7 9 9 3
*/

• Subtask 1: 40 / 100