Submission #98123

#	Time	Username	Problem	Language	Result	Execution time	Memory
98123		jasony123123	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	294 ms	13432 KiB

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 (stderr)

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 / 100