Submission #774616

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
774616	2023-07-05T22:40:57 Z	xjonwang	Job Scheduling (CEOI12_jobs)	C++17	25 / 100	345 ms	20180 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 && i<m) {
		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 true;
}

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

25.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	26 ms	3192 KB	Output isn't correct
2	Incorrect	34 ms	3164 KB	Output isn't correct
3	Incorrect	27 ms	3232 KB	Output isn't correct
4	Incorrect	27 ms	3220 KB	Output isn't correct
5	Incorrect	27 ms	3192 KB	Output isn't correct
6	Incorrect	32 ms	3240 KB	Output isn't correct
7	Incorrect	27 ms	3192 KB	Output isn't correct
8	Incorrect	27 ms	3252 KB	Output isn't correct
9	Incorrect	121 ms	4780 KB	Output isn't correct
10	Incorrect	123 ms	4824 KB	Output isn't correct
11	Correct	25 ms	2136 KB	Output is correct
12	Incorrect	52 ms	4320 KB	Output isn't correct
13	Incorrect	82 ms	6732 KB	Output isn't correct
14	Correct	116 ms	9244 KB	Output is correct
15	Correct	125 ms	10512 KB	Output is correct
16	Correct	165 ms	13260 KB	Output is correct
17	Incorrect	196 ms	16432 KB	Output isn't correct
18	Incorrect	234 ms	16396 KB	Output isn't correct
19	Correct	345 ms	20180 KB	Output is correct
20	Incorrect	195 ms	16460 KB	Output isn't correct