oj.uz

답안 #892720

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
892720 2023-12-25T18:05:35 Z bashNewbie Job Scheduling (CEOI12_jobs) C++17
100 / 100
 225 ms 28620 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define fast_io ios::sync_with_stdio(0), cin.tie(0)
#define pb push_back
template <typename T> using vt = vector<T>;
using vi = vt<int>;
using vvi = vt<vi>;

int main() {
	fast_io;

	int n, d, m; cin >> n >> d >> m;
	vi job(m); vvi in(n);
	for(int j = 0; j < m; j++) {
		int x; cin >> x, --x;
		job[j] = x, in[x].pb(j);
	}
	vi ord;
	for(int i = 0; i < n; i++) for(int x: in[i]) ord.pb(x);

	vvi day;
	auto proc = [&] (int N) {
		day = vvi(n);
		int cur = 0, l = 0;
		while(l < m) {
			int f = N;
			while(l < m && f > 0) {
				int on = job[ord[l]];
				if(on < cur-d) return 0;
				if(on > cur) break;
				day[cur].pb(ord[l]+1), ++l, --f;
			}
			++cur;
		}
		return 1;
	};

	int x = 0, y = m, z;
	while(x < y) {
		z = x+y >> 1;
		if(proc(z)) y = z; else
		x = z+1;
	}
	proc(x);

	cout << x << "\n";
	for(int i = 0; i < n; i++) {
		for(int x: day[i]) cout << x << " ";
		cout << "0\n";
	}
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:43:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   z = x+y >> 1;
      |       ~^~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 3344 KB Output is correct
2 Correct 18 ms 3308 KB Output is correct
3 Correct 18 ms 3340 KB Output is correct
4 Correct 18 ms 3344 KB Output is correct
5 Correct 18 ms 3344 KB Output is correct
6 Correct 18 ms 3340 KB Output is correct
7 Correct 21 ms 3340 KB Output is correct
8 Correct 18 ms 3380 KB Output is correct
9 Correct 27 ms 11804 KB Output is correct
10 Correct 27 ms 12580 KB Output is correct
11 Correct 21 ms 3028 KB Output is correct
12 Correct 41 ms 5228 KB Output is correct
13 Correct 63 ms 8904 KB Output is correct
14 Correct 116 ms 12324 KB Output is correct
15 Correct 106 ms 12632 KB Output is correct
16 Correct 165 ms 18344 KB Output is correct
17 Correct 194 ms 22432 KB Output is correct
18 Correct 210 ms 21956 KB Output is correct
19 Correct 225 ms 28620 KB Output is correct
20 Correct 187 ms 21764 KB Output is correct