Submission #677974

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
677974	2023-01-04T19:46:29 Z	KenHuang	Job Scheduling (CEOI12_jobs)	C++14	80 / 100	569 ms	45748 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	5520 KB	Output is correct
2	Correct	44 ms	5524 KB	Output is correct
3	Correct	44 ms	5532 KB	Output is correct
4	Correct	44 ms	5544 KB	Output is correct
5	Correct	43 ms	5516 KB	Output is correct
6	Correct	45 ms	5524 KB	Output is correct
7	Correct	45 ms	5544 KB	Output is correct
8	Correct	47 ms	5520 KB	Output is correct
9	Correct	196 ms	12140 KB	Output is correct
10	Correct	186 ms	12224 KB	Output is correct
11	Correct	38 ms	5792 KB	Output is correct
12	Correct	77 ms	10604 KB	Output is correct
13	Correct	117 ms	16640 KB	Output is correct
14	Correct	195 ms	22904 KB	Output is correct
15	Correct	220 ms	24404 KB	Output is correct
16	Correct	280 ms	31024 KB	Output is correct
17	Runtime error	344 ms	39968 KB	Memory limit exceeded
18	Runtime error	335 ms	41624 KB	Memory limit exceeded
19	Runtime error	569 ms	45748 KB	Memory limit exceeded
20	Runtime error	347 ms	39996 KB	Memory limit exceeded