oj.uz

답안 #98123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98123 2019-02-20T21:49:49 Z jasony123123 Job Scheduling (CEOI12_jobs) C++11
100 / 100
 294 ms 13432 KB 
#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

# 결과 실행 시간 메모리 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