Submission #98123

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98123	2019-02-20T21:49:49 Z	jasony123123	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	294 ms	13432 KB

jobs

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <array>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else
#endif
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll INF = 1e14;
/***************************ceoi2012_Day1_jobs.cpp*******************************/

int N, D, M;
v<int> jobs[100000];

bool isPossible(int mach) {
	queue<int> q; // <time>
	FOR(i, 0, N) {
		for (auto j : jobs[i]) q.push(i);
		int reps = min(mach, (int)q.size());
		FOR(x, 0, reps) {
			int cur = q.front();
			q.pop();
			if (i > D + cur)
				return 0;
		}
	}
	return q.empty();
}

void print(int mach) {
	cout << mach << "\n";
	queue<int> q; // <id>
	FOR(i, 0, N) {
		for (auto j : jobs[i]) q.push(j);
		int reps = min(mach, (int)q.size());
		FOR(x, 0, reps) {
			int cur = q.front();
			cout << cur << " ";
			q.pop();
		}
		cout << "0\n";
	}
}

int main() {
	io();
	cin >> N >> D >> M;
	FORE(i, 1, M) {
		int day; cin >> day;
		jobs[day - 1].push_back(i);
	}

	int lo = 1, hi = M;
	while (lo < hi) {
		int mi = (lo + hi) / 2;
		if (isPossible(mi) == false) lo = mi + 1;
		else hi = mi;
	}

	print(lo);
}

Compilation message

jobs.cpp: In function 'bool isPossible(int)':
jobs.cpp:47:13: warning: unused variable 'j' [-Wunused-variable]
   for (auto j : jobs[i]) q.push(i);
             ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	4092 KB	Output is correct
2	Correct	34 ms	4080 KB	Output is correct
3	Correct	28 ms	4184 KB	Output is correct
4	Correct	33 ms	4084 KB	Output is correct
5	Correct	31 ms	4104 KB	Output is correct
6	Correct	26 ms	4092 KB	Output is correct
7	Correct	29 ms	4336 KB	Output is correct
8	Correct	26 ms	4084 KB	Output is correct
9	Correct	38 ms	4088 KB	Output is correct
10	Correct	31 ms	4088 KB	Output is correct
11	Correct	31 ms	3836 KB	Output is correct
12	Correct	51 ms	4984 KB	Output is correct
13	Correct	76 ms	6876 KB	Output is correct
14	Correct	120 ms	8212 KB	Output is correct
15	Correct	119 ms	9080 KB	Output is correct
16	Correct	189 ms	10768 KB	Output is correct
17	Correct	248 ms	12664 KB	Output is correct
18	Correct	208 ms	12508 KB	Output is correct
19	Correct	232 ms	13432 KB	Output is correct
20	Correct	294 ms	12664 KB	Output is correct