oj.uz

답안 #774617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
774617 2023-07-05T22:42:04 Z xjonwang Job Scheduling (CEOI12_jobs) C++17
100 / 100
 354 ms 20300 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) {
		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

# 결과 실행 시간 메모리 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