Submission #36686

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
36686	2017-12-13T08:18:29 Z	RockyB	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	749 ms	22592 KB

jobs

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)1e6 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, d, m;
pair <int, int> a[N];
int cnt[(int)1e5 + 7];

bool check(int total) {
	memset(cnt, 0, sizeof(cnt));
	for (int i = 1; i <= m; i++) {
		bool ok = 0;
		for (int j = a[i].f; j <= a[i].f + d; j++) {
			if (cnt[j] < total) {
				cnt[j]++;
				ok = 1;
				break;
			}
		}
		if (!ok) return 0;
	}
	return 1;
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	scanf ("%d%d%d", &n, &d, &m);
	for (int i = 1; i <= m; i++) {
		scanf ("%d", &a[i].f);
		a[i].s = i;
	}
	sort (a + 1, a + 1 + m);
	int l = 1, r = m, res = m;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) res = mid, r = mid - 1;
		else l = mid + 1;
	}
	{
		memset(cnt, 0, sizeof(cnt));
		vector < pair <int, int> > ans;
		for (int i = 1; i <= m; i++) {
			for (int j = a[i].f; j <= a[i].f + d; j++) {
				if (cnt[j] < res) {
					cnt[j]++;
					ans.pb({j, a[i].s});
					break;
				}
			}
		}
		printf ("%d\n", res);
		sort(all(ans));
		int ptr = 0;
		for (int i = 1; i <= n; i++) {
			while (ptr < sz(ans) && ans[ptr].f < i) ptr++;
			while (ptr < sz(ans) && ans[ptr].f == i) {
				printf ("%d ", ans[ptr++].s);
			}
			printf ("0\n");
		}
	}
	ioi
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:57:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d%d", &n, &d, &m);
                              ^
jobs.cpp:59:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d", &a[i].f);
                        ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	11840 KB	Output is correct
2	Correct	29 ms	11840 KB	Output is correct
3	Correct	33 ms	11840 KB	Output is correct
4	Correct	36 ms	11840 KB	Output is correct
5	Correct	29 ms	11840 KB	Output is correct
6	Correct	39 ms	11840 KB	Output is correct
7	Correct	33 ms	11840 KB	Output is correct
8	Correct	33 ms	11840 KB	Output is correct
9	Correct	53 ms	11840 KB	Output is correct
10	Correct	56 ms	11840 KB	Output is correct
11	Correct	49 ms	11840 KB	Output is correct
12	Correct	133 ms	13376 KB	Output is correct
13	Correct	169 ms	16448 KB	Output is correct
14	Correct	749 ms	16448 KB	Output is correct
15	Correct	249 ms	16448 KB	Output is correct
16	Correct	283 ms	22592 KB	Output is correct
17	Correct	443 ms	22592 KB	Output is correct
18	Correct	419 ms	22592 KB	Output is correct
19	Correct	466 ms	22592 KB	Output is correct
20	Correct	436 ms	22592 KB	Output is correct