Submission #774617

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
774617	2023-07-05T22:42:04 Z	xjonwang	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	354 ms	20300 KB

jobs

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

#define ll long long
#define ld long double
#define ar array

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()
#define pll pair<ll, ll>

#define F_OR(i, a, b, s) for (int i = (a); (s) > 0 ? i < (b) : i > (b); i += (s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto &x : a)

template <class T>
bool umin(T &a, const T &b)
{
	return b < a ? a = b, 1 : 0;
}
template <class T>
bool umax(T &a, const T &b)
{
	return a < b ? a = b, 1 : 0;
}

ll FIRSTTRUE(function<bool(ll)> f, ll lb, ll rb)
{
	while (lb < rb)
	{
		ll mb = (lb + rb) / 2;
		f(mb) ? rb = mb : lb = mb + 1;
	}
	return lb;
}
ll LASTTRUE(function<bool(ll)> f, ll lb, ll rb)
{
	while (lb < rb)
	{
		ll mb = (lb + rb + 1) / 2;
		f(mb) ? lb = mb : rb = mb - 1;
	}
	return lb;
}

template <class A>
void read(vt<A> &v);
template <class A, size_t S>
void read(ar<A, S> &a);
template <class A, class B>
void read(pair<A, B> &x);
template <class T>
void read(T &x)
{
	cin >> x;
}
void read(double &d)
{
	string t;
	read(t);
	d = stod(t);
}
void read(long double &d)
{
	string t;
	read(t);
	d = stold(t);
}
template <class H, class... T>
void read(H &h, T &...t)
{
	read(h);
	read(t...);
}
template <class A>
void read(vt<A> &x)
{
	EACH(a, x)
	read(a);
}
template <class A, size_t S>
void read(array<A, S> &x)
{
	EACH(a, x)
	read(a);
}
template <class A, class B>
void read(pair<A, B> &x)
{
	cin >> x.first >> x.second;
}

string to_string(char c)
{
	return string(1, c);
}
string to_string(bool b)
{
	return b ? "true" : "false";
}
string to_string(const char *s)
{
	return string(s);
}
string to_string(string s)
{
	return s;
}
string to_string(vt<bool> v)
{
	string res;
	FOR(sz(v))
	res += char('0' + v[i]);
	return res;
}

template <size_t S>
string to_string(bitset<S> b)
{
	string res;
	FOR(S)
	res += char('0' + b[i]);
	return res;
}
template <class T>
string to_string(T v)
{
	bool f = 1;
	string res;
	EACH(x, v)
	{
		if (!f)
			res += ' ';
		f = 0;
		res += to_string(x);
	}
	return res;
}
template <class A, class B>
string to_string(pair<A, B> &x)
{
	return to_string(x.first) + ' ' + to_string(x.second);
}

template <class A>
void write(A x)
{
	cout << to_string(x);
}
template <class H, class... T>
void write(const H &h, const T &...t)
{
	write(h);
	write(t...);
}
void print()
{
	write("\n");
}
template <class H, class... T>
void print(const H &h, const T &...t)
{
	write(h);
	if (sizeof...(t))
		write(' ');
	print(t...);
}

vt<pair<int, int>> v;
vt<vt<int>> ans;
ll n, d, m;

bool check(ll a) {
	ans.assign(n, vt<int>());
	queue<pll> q;
	int t=1, i=0;
	while (t<=n) {
		int j;
		for (j=0; j<a && q.size(); j++) {
			if (t>q.front().first) return false;
			ans[t-1].pb(q.front().second); q.pop();
		}
		for (; j<a && v[i].first==t; j++, i++) {
			ans[t-1].pb(v[i].second+1);
		}
		for (; v[i].first==t; i++) {
			q.push({t+d, v[i].second+1});
		}
		t++;
	}
	return q.size()==0;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	read(n, d, m);
	v.resize(m);
	FOR(m) {
		cin >> v[i].first;
		v[i].second=i;
	}
	sort(all(v));
	ll a=FIRSTTRUE(check, 1, m);
	check(a);
	print(a);
	EACH(x, ans) {
		EACH(y, x) cout << y << " ";
		cout << "0" << endl;
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	2956 KB	Output is correct
2	Correct	32 ms	2956 KB	Output is correct
3	Correct	33 ms	2956 KB	Output is correct
4	Correct	32 ms	2956 KB	Output is correct
5	Correct	32 ms	2956 KB	Output is correct
6	Correct	33 ms	2960 KB	Output is correct
7	Correct	32 ms	2956 KB	Output is correct
8	Correct	40 ms	2956 KB	Output is correct
9	Correct	132 ms	4796 KB	Output is correct
10	Correct	132 ms	5028 KB	Output is correct
11	Correct	26 ms	2168 KB	Output is correct
12	Correct	54 ms	4480 KB	Output is correct
13	Correct	89 ms	6752 KB	Output is correct
14	Correct	118 ms	9792 KB	Output is correct
15	Correct	125 ms	10508 KB	Output is correct
16	Correct	160 ms	13200 KB	Output is correct
17	Correct	194 ms	16416 KB	Output is correct
18	Correct	223 ms	16628 KB	Output is correct
19	Correct	354 ms	20300 KB	Output is correct
20	Correct	196 ms	16476 KB	Output is correct