Submission #98122

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98122	2019-02-20T21:48:19 Z	jasony123123	Job Scheduling (CEOI12_jobs)	C++11	70 / 100	283 ms	13536 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;
		}
	}
}

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);
             ^
jobs.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	4212 KB	Output is correct
2	Correct	26 ms	4092 KB	Output is correct
3	Correct	31 ms	4212 KB	Output is correct
4	Correct	38 ms	4220 KB	Output is correct
5	Correct	27 ms	4092 KB	Output is correct
6	Correct	27 ms	4208 KB	Output is correct
7	Correct	44 ms	4212 KB	Output is correct
8	Correct	29 ms	4092 KB	Output is correct
9	Correct	32 ms	4088 KB	Output is correct
10	Correct	33 ms	4092 KB	Output is correct
11	Incorrect	26 ms	3832 KB	Output isn't correct
12	Incorrect	48 ms	4984 KB	Output isn't correct
13	Correct	77 ms	6904 KB	Output is correct
14	Incorrect	132 ms	8056 KB	Output isn't correct
15	Correct	125 ms	9160 KB	Output is correct
16	Incorrect	187 ms	10616 KB	Output isn't correct
17	Incorrect	223 ms	12504 KB	Output isn't correct
18	Correct	212 ms	12540 KB	Output is correct
19	Correct	283 ms	13536 KB	Output is correct
20	Incorrect	222 ms	12536 KB	Output isn't correct