oj.uz

Submission #775751

# Submission time Handle Problem Language Result Execution time Memory
775751 2023-07-06T21:13:04 Z NK_ Job Scheduling (CEOI12_jobs) C++17
100 / 100
 176 ms 26852 KB 
// 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;

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

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

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

			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)) hi = mid;
		else lo = mid + 1;
	}

	check(lo, 1);

	printf("%d\n", lo);
	for(int i = 0; i < N; i++) {
		for(auto &x : ans[i]) printf("%d ", x + 1);
		printf("%d\n", 0);
	}

    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:21:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  int N, D, M; scanf("%d%d%d", &N, &D, &M);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:23:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   int t; scanf("%d", &t); --t;
      |          ~~~~~^~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7380 KB Output is correct
2 Correct 19 ms 7468 KB Output is correct
3 Correct 19 ms 7440 KB Output is correct
4 Correct 20 ms 7360 KB Output is correct
5 Correct 20 ms 7448 KB Output is correct
6 Correct 19 ms 7372 KB Output is correct
7 Correct 19 ms 7364 KB Output is correct
8 Correct 22 ms 7376 KB Output is correct
9 Correct 27 ms 7620 KB Output is correct
10 Correct 27 ms 7572 KB Output is correct
11 Correct 21 ms 7468 KB Output is correct
12 Correct 38 ms 9884 KB Output is correct
13 Correct 55 ms 13540 KB Output is correct
14 Correct 101 ms 16076 KB Output is correct
15 Correct 115 ms 17124 KB Output is correct
16 Correct 123 ms 20120 KB Output is correct
17 Correct 150 ms 25420 KB Output is correct
18 Correct 143 ms 25284 KB Output is correct
19 Correct 176 ms 26852 KB Output is correct
20 Correct 145 ms 25416 KB Output is correct