Submission #484516

#	Time	Username	Problem	Language	Result	Execution time	Memory
484516		1potato2potato	Job Scheduling (CEOI12_jobs)	C++17	75 / 100	406 ms	61248 KiB

jobs

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

using ll = long long;

using vi = vector<ll>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (ll) (x).size()

using pi = pair<ll,ll>;
#define f first
#define s second
#define mp make_pair

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

ll n, d, m;
vector<pi> jobs;

pair<bool, vector<vi>> feas(ll k) {
	ll jobnum = 0;
	vector<vi> ans(n);
	for (ll i=1; i<=n; i++) {
		for (ll j = 0; j < k; j++) {
			if (jobs[jobnum].f > i) break;

			if (jobs[jobnum].f + d >= i) {
				ans[i - 1].push_back(jobs[jobnum].s);
				jobnum++;
			} else {
				// can't fit this job
				return mp(false, ans);
			}

			if (jobnum == m) {
				// finished all jobs
				return mp(true, ans);
			}
		}
	}
	return mp(false, ans);
}
int main() {
	setIO();
	cin >> n >> d >> m;

	for (ll i = 0; i < m; i++) {
		ll day;
		cin >> day;
		jobs.pb({day, i + 1});
	}
	sort(all(jobs));

	ll lo = 1, hi = m;
	vector<vi> ret;
	pair<bool, vector<vi>> res;
	while (lo < hi) {
		ll mid = (lo + hi) / 2;
		res = feas(mid);
		if(res.f) {
			hi = mid;
			ret = res.s;
		} else {
			lo = mid + 1;
		}
	}
	cout << lo << "\n";

	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < sz(ret[i]); j++) {
			cout << ret[i][j] << " ";
		}
		cout << "0\n";
	}
}

Compilation message (stderr)

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

• Subtask 1: 75 / 100