Submission #757283

#	Time	Username	Problem	Language	Result	Execution time	Memory
757283		yash_9a3b	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	490 ms	21988 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
 
using i64 = int;
i64 const &N_ = 1e5 + 1; 
i64 const &M_ = 1e6 + 1;
 
i64 N, D, M;
vector < i64 > ans[N_];
vector < pair < i64, i64 >> DAYS;
 
bool check(i64 machine) {
    i64 d = 0;
    i64 cnt = 0;
    for (i64 i = 0; i < (i64) DAYS.size(); ) {
        i64 j = i;
        bool ok = false;
        i64 val = max(DAYS[i].first, d + 1);
        for (i64 cnt_ = 0; j < M and DAYS[j].first < val + 1 and DAYS[j].first >= val - D and cnt_ < machine; ++ cnt_, ++ j) {
            // Let it be
            cnt ++;
            ok = true;
        }
        if (! ok) return false;
        i = j;
        d = val;
    }
    return cnt == M;
}
 
void get_ans(i64 machine) {
    i64 d = 0;
    for (i64 i = 0; i < (i64) DAYS.size(); ) {
        i64 j = i;
        bool ok = false;
        i64 val = max(DAYS[i].first, d + 1);
        for (i64 cnt_ = 0; j < M and DAYS[j].first < val + 1 and DAYS[j].first >= val - D and cnt_ < machine; ++ cnt_, ++ j) {
            // Let it be
            ans[val].push_back(DAYS[j].second);
            ok = true;
        }
        if (! ok) return ;
        i = j;
        d = val;
    }
}
 
void Solution() {
    cin >> N >> D >> M;
    for (i64 i = 0; i < M; ++ i) {
        i64 a;
        cin >> a;
        DAYS.push_back(make_pair(a, i + 1));
    }
 
    i64 save = -1;
    sort(DAYS.begin(), DAYS.end());
 
    i64 l = 0, r = M;
    while (l < r + 1) {
        i64 mid = (l + r) / 2;
        if (check(mid)) save = mid, r = mid - 1;
        else l = mid + 1;
    }
 
    get_ans(save);
    cout << save << endl;
    for (i64 i = 1; i < N + 1; ++ i) {
        for (auto it : ans[i]) {
            cout << it << ' ';
        }
        cout << '0' << endl;
    }
}
 
int main() {
    Solution();
    return 0;
}

• Subtask 1: 100 / 100