Submission #563589

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
563589	2022-05-17T16:01:21 Z	Codurr	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	372 ms	22540 KB

jobs

#include "bits/stdc++.h"
using namespace std;

#define int long long //Avoid if time complexity very close to limit
#define ll long long
#define sz(x) (int)((x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define f first
#define s second

void setIO(string s = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s)) {
		freopen((s + ".in").c_str(), "r", stdin);
		freopen((s + ".out").c_str(), "w", stdout);
	}
}

//Imp consts
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 1;
const int INF = 1e18 + 5;
const double pi = 3.14159265358979323846;
const double ep = 1e-20;

signed main() {
	setIO();
	int n, d, m;
	cin >> n >> d >> m;
	vector<int> st(n + 1), en(n + 1);
	vector<pair<int, int>> task;
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		task.push_back({x, i + 1});
		st[x]++;
		en[x + d]++;
	}
	sort(all(task));
	int l = 0, r = 1e7;
	while (r > l + 1) {
		int m = l + (r - l) / 2;
		int done = 0, due = 0;
		bool ok = 1;
		for (int i = 1; i <= n; i++) {
			due += st[i];
			int x = due;
			due -= min(m, x);
			done += min(m, x);
			if (en[i]) {
				if (done < en[i]) {
					ok = 0;
					break;
				}
				done -= en[i];
			}
		}
		if (ok)
			r = m;
		else
			l = m;
	}
	cout << r << '\n';;
	l = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= r; j++) {
			if (l < sz(task) && task[l].f <= i) {
				cout << task[l].s << " ";
				l++;
			}
		}
		cout << "0\n" ;
	}
	return 0;
}

Compilation message

jobs.cpp: In function 'void setIO(std::string)':
jobs.cpp:15:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:16:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   freopen((s + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	358 ms	2772 KB	Output is correct
2	Correct	372 ms	2876 KB	Output is correct
3	Correct	352 ms	2892 KB	Output is correct
4	Correct	353 ms	2768 KB	Output is correct
5	Correct	353 ms	2772 KB	Output is correct
6	Correct	360 ms	2768 KB	Output is correct
7	Correct	358 ms	2892 KB	Output is correct
8	Correct	354 ms	2768 KB	Output is correct
9	Correct	349 ms	4412 KB	Output is correct
10	Correct	336 ms	4344 KB	Output is correct
11	Correct	24 ms	2548 KB	Output is correct
12	Correct	47 ms	4880 KB	Output is correct
13	Correct	74 ms	8688 KB	Output is correct
14	Correct	99 ms	9552 KB	Output is correct
15	Correct	123 ms	11588 KB	Output is correct
16	Correct	153 ms	16944 KB	Output is correct
17	Correct	181 ms	16928 KB	Output is correct
18	Correct	204 ms	18600 KB	Output is correct
19	Correct	288 ms	22540 KB	Output is correct
20	Correct	186 ms	16956 KB	Output is correct