Submission #545128

#	Time	Username	Problem	Language	Result	Execution time	Memory
545128		rainboy	Job Scheduling (CEOI12_jobs)	C11	100 / 100	155 ms	17484 KiB

jobs

#include <stdio.h>

#define N	100000
#define M	1000000

int ii[M], hh[M], kk[N + 1], ll[N + 1], n, d, m;

int solve(int k, int print) {
	int h, i, j;

	if (!print)
		for (i = 0, j = 0; j < n; j++) {
			int k_;

			k_ = k;
			ll[j] = kk[j];
			while (i <= j && k_ >= ll[i])
				k_ -= ll[i++];
			if (i <= j)
				ll[i] -= k_;
			if (j - i >= d)
				return 0;
		}
	else
		for (i = 0, h = 0; i < n; i++) {
			int k_ = k;

			while (h < m && ii[hh[h]] <= i && k_--)
				printf("%d ", hh[h++] + 1);
			printf("0\n");
		}
	return 1;
}

int main() {
	int h, i, lower, upper;

	scanf("%d%d%d", &n, &d, &m);
	for (h = 0; h < m; h++) {
		scanf("%d", &ii[h]), ii[h]--;
		kk[ii[h]]++;
	}
	for (i = 1; i <= n; i++)
		ll[i] = ll[i - 1] + kk[i - 1];
	for (h = 0; h < m; h++)
		hh[ll[ii[h]]++] = h;
	lower = 0, upper = m;
	while (upper - lower > 1) {
		int k = (lower + upper) / 2;

		if (solve(k, 0))
			upper = k;
		else
			lower = k;
	}
	printf("%d\n", upper);
	solve(upper, 1);
	return 0;
}

Compilation message (stderr)

jobs.c: In function 'main':
jobs.c:38:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d%d", &n, &d, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.c:40:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d", &ii[h]), ii[h]--;
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100