Submission #774614

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
774614	2023-07-05T22:35:22 Z	xjonwang	Job Scheduling (CEOI12_jobs)	C++17	20 / 100	351 ms	34636 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<pll> v;
vt<vt<ll>> ans;
ll n, d, m;

bool check(ll a) {
	ans.assign(n, vt<ll>());
	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

20.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	27 ms	4532 KB	Output isn't correct
2	Incorrect	27 ms	4496 KB	Output isn't correct
3	Incorrect	27 ms	4520 KB	Output isn't correct
4	Incorrect	28 ms	4504 KB	Output isn't correct
5	Incorrect	28 ms	4468 KB	Output isn't correct
6	Incorrect	27 ms	4500 KB	Output isn't correct
7	Incorrect	27 ms	4488 KB	Output isn't correct
8	Incorrect	28 ms	4520 KB	Output isn't correct
9	Incorrect	123 ms	6164 KB	Output isn't correct
10	Incorrect	125 ms	6220 KB	Output isn't correct
11	Correct	28 ms	3908 KB	Output is correct
12	Incorrect	60 ms	7632 KB	Output isn't correct
13	Incorrect	81 ms	12108 KB	Output isn't correct
14	Correct	118 ms	16548 KB	Output is correct
15	Correct	128 ms	19132 KB	Output is correct
16	Correct	176 ms	24532 KB	Output is correct
17	Incorrect	212 ms	30384 KB	Output isn't correct
18	Incorrect	241 ms	29800 KB	Output isn't correct
19	Runtime error	351 ms	34636 KB	Memory limit exceeded
20	Incorrect	216 ms	30468 KB	Output isn't correct