oj.uz

Submission #774615

# Submission time Handle Problem Language Result Execution time Memory
774615 2023-07-05T22:39:16 Z xjonwang Job Scheduling (CEOI12_jobs) C++17
0 / 100
 332 ms 20116 KB 
#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 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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 2460 KB Output isn't correct
2 Incorrect 27 ms 2468 KB Output isn't correct
3 Incorrect 27 ms 2472 KB Output isn't correct
4 Incorrect 27 ms 2492 KB Output isn't correct
5 Incorrect 27 ms 2560 KB Output isn't correct
6 Incorrect 27 ms 2520 KB Output isn't correct
7 Incorrect 27 ms 2588 KB Output isn't correct
8 Incorrect 27 ms 2460 KB Output isn't correct
9 Incorrect 122 ms 4808 KB Output isn't correct
10 Incorrect 122 ms 4788 KB Output isn't correct
11 Incorrect 26 ms 2260 KB Output isn't correct
12 Incorrect 51 ms 4200 KB Output isn't correct
13 Incorrect 75 ms 6628 KB Output isn't correct
14 Incorrect 122 ms 9656 KB Output isn't correct
15 Incorrect 127 ms 10752 KB Output isn't correct
16 Incorrect 166 ms 13200 KB Output isn't correct
17 Incorrect 192 ms 16300 KB Output isn't correct
18 Incorrect 217 ms 16460 KB Output isn't correct
19 Incorrect 332 ms 20116 KB Output isn't correct
20 Incorrect 194 ms 16276 KB Output isn't correct