제출 #502609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
502609		banterbry	Job Scheduling (CEOI12_jobs)	C++17	50 / 100	244 ms	34380 KiB

jobs

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

int N, M, D;
pi req[1000010];
vector<int> ans[100010];

int good(int x) {
    int day = 1, cnt = 0;
    for (int i = 1; i <= M; ++i) {
        ++cnt;
        if (cnt > x) {
            cnt = 1;
            ++day;
        }
        if (day - req[i].fi > D) return 0;
    }
    return 1;
}

int32_t main() {
    fast;
    cin >> N >> D >> M;
    for (int i = 1; i <= M; ++i) {
        cin >> req[i].fi;
        req[i].si = i;
    }
    sort(req + 1, req + 1 + M);
    int lo = 0, hi = M + 1;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (good(mid)) hi = mid;
        else lo = mid;
    }
    int day = 1, cnt = 0;
    for (int i =1; i <= M; ++i) {
        ++cnt;
        if (cnt > hi) {
            cnt = 1;
            ++day;
        }
        ans[day].pb(req[i].si);
    }
    cout << hi << '\n';
    for (int i = 1; i <= N; ++i) {
        for (auto j: ans[i]) cout << j << ' ';
        cout << 0 << '\n';
    }
    return 0;
}

• Subtask 1: 50 / 100