Submission #524317

#	Time	Username	Problem	Language	Result	Execution time	Memory
524317		Luucifer	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	673 ms	26988 KiB

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 / 100