Submission #658648

#	Time	Username	Problem	Language	Result	Execution time	Memory
658648		stephenc	Job Scheduling (CEOI12_jobs)	C++17	30 / 100	357 ms	21136 KiB

jobs

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll=long long;

bool validate(vector<pair<int,int>>& requests, ll num_machines, int day_num, int max_delay) {
    int requests_today=0;
    int cur_day=1;
    // cout<<1<<": ";
    for (auto& p : requests) {
        // cout<<"("<<p.first<<", "<<p.second<<") ";
        if (p.first>cur_day) {
            requests_today=0;
            cur_day=p.first;
        }
        requests_today++;
        if (requests_today>=num_machines) {
            cur_day++;
            requests_today=0;
            // cout<<"\n"<<cur_day<<": ";
        }
        if (cur_day-p.first>max_delay||cur_day>day_num) return false;
    }
    return true;
}

int main() {
    int n, d, m;
    cin>>n>>d>>m;
    vector<pair<int,int>> requests;
    for (int i=1; i<=m; ++i) {
        int r;
        cin>>r;
        requests.push_back({r, i});
    }
    sort(begin(requests), end(requests));
    // for (auto& p : requests) {
    //     cout<<p.first<<" "<<p.second<<"\n";
    // }
    // ll mid=1e6;
    // cout<<validate(requests, mid, n, d)<<"\n";

    ll lo=1, hi=1e6, sol=1e6; //number of machines
    while (lo<=hi) {
        ll mid=lo+(hi-lo)/2; //number of machines
        if (validate(requests, mid, n, d)) {
            sol=min(sol, mid);
            hi=mid-1;
        } else {
            lo=mid+1;
        }
    }
    cout<<sol<<"\n";
    int request_num=0;
    for (int i=1; i<=n; ++i) {
        for (int j=0; j<sol; ++j) {
            if (requests[request_num].first>i) break;
            if (request_num<m) cout<<requests[request_num].second<<" ";
            request_num++;
        }
        cout<<0<<"\n";
    }
}
/*
8 2 12
1  2  4  2  1  3  5  6  2  3  6  4
1  2  3  4  5  6  7  8  9  10 11 12
1: (1, 1) (1, 5) 
2: (2, 2) (2, 4)
3: (2, 9) (3, 6)
4: (3, 10) (4, 3)
5: (4, 12) (5, 7)
6: (6, 8) (6, 11)
7: 1

num_machines = 2
1 1 1 
1 1 5
2 2 2
2 2 4
3 2 9
3 3 6
4 3 10
4 4 3
5 4 12
5 5 7
6 6 8
6 6 11

binary search through number of machines needed
validate if constraints are satisfied
*/

• Subtask 1: 30 / 100