Submission #120989

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
120989	2019-06-25T21:46:06 Z	MB81	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	358 ms	14408 KB

jobs

#include <bits/stdc++.h>

using namespace std;
typedef long long int64;
typedef pair<int,int> pii;
typedef pair<int64,int> pii32;
typedef pair<int64,int64> pii64;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int maxn = 1e5+10;
const int64 MO = 1e9+7;
const int64 IN = 1e9;

queue <pii> q1;
vector <int> v1[maxn];
int n, d, m;

int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> d >> m;
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		v1[x].PB(i + 1);
	}
	int l, r, mid;
	l = 0;
	r = m;
	while (r - l > 1) {
		mid = (l + r) >> 1;
		while(sz(q1)) q1.pop();
		bool ok = 1;
		for (int i = 1; i <= n; i++) {
			if (sz(q1) && q1.front().F < i - d)
				ok = 0;
			for (auto x : v1[i])
				q1.push(MP(i, x));
			for (int t = 0; t < mid && sz(q1); t++)
				q1.pop();
		}
		if (sz(q1))
			ok = 0;
		if (ok)	
			r = mid;
		else
			l = mid;
	}
	cout << r << "\n";
	while(sz(q1)) q1.pop();
	for (int i = 1; i <= n; i++) {
		for (auto x : v1[i])
			q1.push(MP(i, x));
		for (int t = 0; t < r && sz(q1); t++) {
			cout << q1.front().S << " ";
			q1.pop();
		}
		cout << "0\n";
	}

}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	38 ms	4600 KB	Output is correct
2	Correct	39 ms	4596 KB	Output is correct
3	Correct	38 ms	4604 KB	Output is correct
4	Correct	39 ms	4596 KB	Output is correct
5	Correct	37 ms	4596 KB	Output is correct
6	Correct	38 ms	4468 KB	Output is correct
7	Correct	39 ms	4596 KB	Output is correct
8	Correct	37 ms	4592 KB	Output is correct
9	Correct	44 ms	4472 KB	Output is correct
10	Correct	45 ms	4396 KB	Output is correct
11	Correct	37 ms	3960 KB	Output is correct
12	Correct	79 ms	5220 KB	Output is correct
13	Correct	114 ms	6748 KB	Output is correct
14	Correct	189 ms	8964 KB	Output is correct
15	Correct	192 ms	8952 KB	Output is correct
16	Correct	275 ms	12292 KB	Output is correct
17	Correct	322 ms	14252 KB	Output is correct
18	Correct	312 ms	12460 KB	Output is correct
19	Correct	358 ms	13424 KB	Output is correct
20	Correct	328 ms	14408 KB	Output is correct