제출 #775753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
775753		NK_	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	68 ms	26908 KiB

jobs

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

template<class T> using V = vector<T>;

const int MX = 1e6+6;
const int nax = 1e5+5;


int d[10];
int read() {
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		ch = getchar();
	}
	int v = 0;
	while ('0' <= ch && ch <= '9') {
		v = v * 10 + (int) (ch - '0');
		ch = getchar();
	}
	return v;
}
 
void write(int x, bool newline) {
	int len = 0;
	while (x > 0) {
		d[len++] = x % 10;
		x /= 10;
	}
	for (int i = len - 1; i >= 0; i--) {
		putchar('0' + d[i]);
	}
	if (len == 0) {
		putchar('0');
	}
	if (newline) putchar('\n');
	else putchar(' ');
}

pair<int, int> in[MX];
V<int> C[nax], ans[nax];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N = read(), D = read(), M = read(); 
	for(int i = 0; i < M; i++) {
		int t = read() - 1;
		C[t].pb(i);
	}

	function<bool(int, bool)> check = [&](int x, bool CREATE) {
		int cur = 0, len = 0;
		for(int i = 0; i < N; i++) {
			if (cur < len && in[cur].first <= i) return false;

			int end = i + D + 1;
			for(auto &c : C[i]) in[len++] = {end, c};

			if (CREATE) {
				int left = x;
				while(left-- && cur < len) ans[i].push_back(in[cur++].second);
			} else cur = min(len, cur + x);
		}

		return cur == len;
	};

	int lo = 1, hi = M;
	while(lo < hi) {
		int mid = (lo + hi) / 2;
		if (check(mid, false)) hi = mid;
		else lo = mid + 1;
	}

	check(lo, 1);

	write(lo, true);
	for(int i = 0; i < N; i++) {
		for(auto &x : ans[i]) write(x + 1, 0);
		write(0, 1);
	}

    return 0;
}

• Subtask 1: 100 / 100