oj.uz

답안 #96296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96296 2019-02-08T03:38:16 Z shoemakerjo Job Scheduling (CEOI12_jobs) C++14
100 / 100
 968 ms 30584 KB 
#include <bits/stdc++.h>

using namespace std;

int N, M, D;
const int maxm = 1000010;
const int maxn = 100010;

vector<int> ac[maxn]; //store indices of all that start at me

int ans[maxm];
int st[maxm]; //store start for all values
vector<int> res[maxn];

bool go(int mid) {
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		for (int v : ac[i]) q.push(v);

		for (int j = 1; j <= mid; j++) {
			if (q.empty()) break;
			if (st[q.front()] + D < i)  return false;
			ans[q.front()] = i;
			q.pop();
		}
	}

	return q.size() == 0;

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> D >> M;
	int cur;
	for (int i = 1; i <= M; i++) {
		cin >> cur;
		st[i] = cur;
		ac[cur].push_back(i);
	}

	int lo = 1;
	int hi = M;
	while (lo < hi) {
		int mid = (lo + hi)/2;
		if (go(mid)) {
			hi = mid;
		}
		else lo = mid+1;
	}
	go(lo);
	for (int i = 1; i <= M; i++) {
		res[ans[i]].push_back(i);
	}

	cout << lo << endl;
	for (int i = 1; i <= N; i++) {
		for (int v : res[i]) cout << v << " ";
		cout << 0 << '\n';
	}
	cout.flush();
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 7764 KB Output is correct
2 Correct 33 ms 7824 KB Output is correct
3 Correct 30 ms 7764 KB Output is correct
4 Correct 47 ms 7880 KB Output is correct
5 Correct 32 ms 7736 KB Output is correct
6 Correct 32 ms 7792 KB Output is correct
7 Correct 31 ms 7892 KB Output is correct
8 Correct 30 ms 7764 KB Output is correct
9 Correct 45 ms 8184 KB Output is correct
10 Correct 61 ms 8028 KB Output is correct
11 Correct 59 ms 7956 KB Output is correct
12 Correct 124 ms 10732 KB Output is correct
13 Correct 183 ms 14820 KB Output is correct
14 Correct 298 ms 18288 KB Output is correct
15 Correct 332 ms 19064 KB Output is correct
16 Correct 409 ms 23160 KB Output is correct
17 Correct 658 ms 29176 KB Output is correct
18 Correct 645 ms 28536 KB Output is correct
19 Correct 968 ms 30584 KB Output is correct
20 Correct 513 ms 29176 KB Output is correct