Submission #96296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
96296	2019-02-08T03:38:16 Z	shoemakerjo	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	968 ms	30584 KB

jobs

#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

#	Verdict	Execution time	Memory	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