Submission #677974

#	Time	Username	Problem	Language	Result	Execution time	Memory
677974		KenHuang	Job Scheduling (CEOI12_jobs)	C++14	80 / 100	569 ms	45748 KiB

jobs

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N, D, M;
vector<pair<ll,ll>>v; // {the day, the i +1 value}
ll ans = 1e6;
vector<vector<ll>>ans_vec;

pair<bool, vector<vector<ll>>>check_valid(ll mid) {
    ll current_request = 0;
    vector<vector<ll>>the_days(N);
    //we can simulate the days from 1 to N
    for (ll day = 1; day <= N; day++){
        //we can only process mid requests before we have to move onto the next day
        for (ll i = 0; i < mid; i++){
            //if the delay + Mi is less than the current day then we can't do nothing
            if (v[current_request].first + D < day){
                return {false, the_days};
            }
            if (v[current_request].first > day) break; //we can go to the next time cus we can't process it at the current time
            the_days[day-1].push_back(v[current_request].second);
            current_request++;
            if (current_request == M){ //if all the requests are processed then we gucci
                return {true, the_days};
            }
        }
    }
    //not all requests can be processed within the N given days
    return {false, the_days};
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> D >> M;
    for (ll i = 0; i < M; i++){
        ll num; cin >> num;
        v.push_back({num, i+1});
    }
    sort(v.begin(), v.end());
    ll lo = 1;
    ll hi = M;
    while (lo <= hi){
        ll mid = lo + (hi-lo)/2;
        //check if mid works and also get the vector output if mid does work
        pair<bool, vector<vector<ll>>>current_results = check_valid(mid);
        if (current_results.first){
            ans = min(ans, mid);
            ans_vec = current_results.second;
            hi = mid-1;
        } else{
            lo = mid+1;
        }
    }
    cout << ans << endl;
    for (auto days : ans_vec){
        for (auto day : days){
            cout << day << " ";
        }
        cout << 0 << endl;
    }
    return 0;
}

• Subtask 1: 80 / 100