Submission #1097085

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1097085	2024-10-06T03:32:34 Z	TrinhKhanhDung	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	213 ms	27728 KB

jobs

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18 + 10
#define INF (ll)1e9
#define MOD (ll)(998244353)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 1e6 + 10;

int N, D, M;
pair<int, int> a[MAX];
int ans[MAX];

void solve(){
    cin >> N >> D >> M;
    for(int i = 1; i <= M; i++){
        cin >> a[i].fi;
        a[i].se = i;
    }

    sort(a + 1, a + M + 1);

    auto OK = [&](int k) -> bool{
        int day = 1, cnt = 0;
        for(int i = 1; i <= M; i++){
            if(day - a[i].fi > D) return false;
            if(maximize(day, a[i].fi)) cnt = 0;
            cnt++;
            ans[a[i].se] = day;
            if(cnt == k){
                day++;
                cnt = 0;
            }
        }
        return true;
    };

    int l = 1, r = M;
    while(l < r){
        int m = (l + r) >> 1;
        if(OK(m)) r = m;
        else l = m + 1;
    }

    OK(r);
    cout << r << '\n';
    vector<vector<int>> trace(N + 3);
    for(int i = 1; i <= M; i++){
        trace[ans[i]].push_back(i);
    }

    for(int i = 1; i <= N; i++){
        for(int x: trace[i]) cout << x << ' ';
        cout << 0 << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("task.inp","r",stdin);
//    freopen("task.out","w",stdout);

    int T = 1;
//    cin >> T;
    for(; T; T--) solve();

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	3164 KB	Output is correct
2	Correct	14 ms	3160 KB	Output is correct
3	Correct	13 ms	3160 KB	Output is correct
4	Correct	13 ms	3164 KB	Output is correct
5	Correct	14 ms	3160 KB	Output is correct
6	Correct	14 ms	3164 KB	Output is correct
7	Correct	15 ms	3164 KB	Output is correct
8	Correct	13 ms	3164 KB	Output is correct
9	Correct	25 ms	5492 KB	Output is correct
10	Correct	29 ms	5712 KB	Output is correct
11	Correct	21 ms	3164 KB	Output is correct
12	Correct	42 ms	5968 KB	Output is correct
13	Correct	69 ms	9412 KB	Output is correct
14	Correct	94 ms	12936 KB	Output is correct
15	Correct	107 ms	13788 KB	Output is correct
16	Correct	137 ms	17492 KB	Output is correct
17	Correct	163 ms	22560 KB	Output is correct
18	Correct	179 ms	23124 KB	Output is correct
19	Correct	213 ms	27728 KB	Output is correct
20	Correct	172 ms	22612 KB	Output is correct