Submission #498158

#	Time	Username	Problem	Language	Result	Execution time	Memory
498158		MohamedFaresNebili	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	350 ms	20108 KiB

jobs

#include<bits/stdc++.h>
 
        using namespace std;
 
        using ll  = long long;
        using ii = pair<int, int>;
        using vi  = vector<int>;
 
        #define pb push_back
        #define ff first
        #define ss second
        #define lb lower_bound
        #define all(x) (x).begin() , (x).end()
 
        int n, d, m; vector<ii> arr;
        bool can(int val) {
            int day[val]{0};
            for(int l = 0, curr = 0; l < m; l++, curr = (curr + 1) % val) {
                if(day[curr] + 1 - arr[l].ff > d) return 0;
                day[curr] = max(day[curr] + 1, arr[l].ff);
            }
            return 1;
        }
 
        int32_t main() {
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            cin >> n >> d >> m;
            for(int l = 0; l < m; l++) {
                int a; cin >> a; arr.pb({a, l});
            }
            sort(all(arr));
            int lo = 0, hi = m, ans = -1;
            while(lo <= hi) {
                int md = (lo + hi + 1) / 2;
                if(can(md)) { ans = md; hi = md - 1; }
                else lo = md + 1;
            }
            cout << ans << "\n";
            vector<int> res[n + 1]; int val[ans]{0};
            for(int l = 0, curr = 0; l < m; l++, curr = (curr + 1) % ans) {
                val[curr] = max(val[curr] + 1, arr[l].ff);
                res[val[curr]].pb(arr[l].ss + 1);
            }
            for(int l = 1; l <= n; l++) {
                for(auto u : res[l])
                    cout << u << " ";
                cout << 0 << "\n";
            }
        }

• Subtask 1: 100 / 100