답안 #524317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
524317	2022-02-09T04:10:01 Z	Luucifer	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	673 ms	26988 KB

jobs

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

// clang-format off
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define endl "\n"
#define pb push_back
#define sz(v) int(v.size())
#define mems(x,y) memset(x,y,sizeof(x))
#define all(x) (x).begin(),(x).end()
#define forn(i,s,e) for(int i = s; i < (e); ++i)
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time__(d)                                                   \
for (                                                                   \
auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
        blockTime.second;                                               \
debug("%s : %lld ms\n ", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false)
const int M = 1e9 + 7;

template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
#ifdef LOCAL
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << '['; for (auto v : vec) os << v << ','; os << ']'; return os; }
#else
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { for (auto v : vec) os << v << ' ';  return os; }
#endif

template <class T> T ABS(const T &x) {return x>0? x:-x;}
ll gcd(ll n1, ll n2) {return n2==0? ABS(n1) : gcd(n2,n1%n2);}
ll lcm(ll n1, ll n2) {return n1==0 && n2==0? 0 : ABS(n1*n2)/gcd(n1,n2);}
ll ceil2(ll a, ll b) {return (a + b - 1) / b;}

template <typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template <typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
template <typename T> vector<T> sorttrunq(vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }
// clang-format on

// int dx[4] = {1,-1,0,0};
// int dy[4] = {0,0,1,-1};

/*
    1. When multiplying always consider the possiblity of overflow.
*/

void solve() {
    int n, d, m;
    cin >> n >> d >> m;
    vi t(m);
    cin >> t;
    vi pos(m);
    iota(all(pos), 0);
    sort(all(pos), [&](int a, int b) { return t[a] < t[b]; });

    vector<vi> tmp(n + 1);
    auto ok = [&](int x) {
        tmp.clear();
        tmp.resize(n + 1);
        deque<int> dq(x, 0);
        for (int idx : pos) {
            int st = max(t[idx], dq.front());
            if (st > t[idx] + d) {
                return false;
            }
            tmp[st].push_back(idx);
            dq.pop_front();
            dq.push_back(st + 1);
        }

        return true;
    };

    int l = 0, r = m + 1;
    vector<vi> ans;
    while (r - l > 1) {
        ll mid = l + (r - l) / 2;
        if (ok(mid)) {
            ans = tmp;
            r = mid;
        } else
            l = mid;
    }
    cout << r << endl;
    for (int i = 1; i <= n; ++i) {
        for (int &el : ans[i]) {
            cout << el + 1 << " ";
        }
        cout << 0 << endl;
    }
}

int main() {
    FASTIO
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	3360 KB	Output is correct
2	Correct	39 ms	3496 KB	Output is correct
3	Correct	38 ms	3360 KB	Output is correct
4	Correct	36 ms	3368 KB	Output is correct
5	Correct	38 ms	3480 KB	Output is correct
6	Correct	37 ms	3432 KB	Output is correct
7	Correct	37 ms	3348 KB	Output is correct
8	Correct	46 ms	3504 KB	Output is correct
9	Correct	57 ms	7716 KB	Output is correct
10	Correct	56 ms	7732 KB	Output is correct
11	Correct	50 ms	2716 KB	Output is correct
12	Correct	116 ms	5252 KB	Output is correct
13	Correct	182 ms	8196 KB	Output is correct
14	Correct	269 ms	11356 KB	Output is correct
15	Correct	304 ms	12536 KB	Output is correct
16	Correct	406 ms	15596 KB	Output is correct
17	Correct	526 ms	19992 KB	Output is correct
18	Correct	579 ms	20652 KB	Output is correct
19	Correct	673 ms	26988 KB	Output is correct
20	Correct	540 ms	19976 KB	Output is correct