Submission #98121

# Submission time Handle Problem Language Result Execution time Memory
98121 2019-02-20T21:43:01 Z jasony123123 Job Scheduling (CEOI12_jobs) C++11
5 / 100
244 ms 13916 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);
		FOR(x, 0, min(mach, (int)q.size())) {
			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);
		FOR(x, 0, min(mach, (int)q.size())) {
			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:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 4564 KB Output isn't correct
2 Incorrect 52 ms 4468 KB Output isn't correct
3 Incorrect 31 ms 4340 KB Output isn't correct
4 Incorrect 40 ms 4600 KB Output isn't correct
5 Incorrect 28 ms 4476 KB Output isn't correct
6 Incorrect 28 ms 4344 KB Output isn't correct
7 Incorrect 28 ms 4440 KB Output isn't correct
8 Incorrect 29 ms 4468 KB Output isn't correct
9 Incorrect 41 ms 4344 KB Output isn't correct
10 Incorrect 37 ms 4352 KB Output isn't correct
11 Incorrect 43 ms 4216 KB Output isn't correct
12 Incorrect 61 ms 5624 KB Output isn't correct
13 Correct 86 ms 7516 KB Output is correct
14 Incorrect 186 ms 8696 KB Output isn't correct
15 Incorrect 88 ms 9592 KB Output isn't correct
16 Incorrect 205 ms 11316 KB Output isn't correct
17 Incorrect 244 ms 13220 KB Output isn't correct
18 Incorrect 226 ms 13088 KB Output isn't correct
19 Incorrect 237 ms 13916 KB Output isn't correct
20 Incorrect 243 ms 13176 KB Output isn't correct