Submission #848039

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
848039	2023-09-11T06:37:44 Z	daoda	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	204 ms	21328 KB

jobs

#include <bits/stdc++.h>

using namespace std;
#define FOR(a, b) for(ll i = a; i < b; i++)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);

typedef long long int ll;
typedef pair<ll, ll> pll; // comments that are mixed
typedef vector<ll> vll; // in with code are placed
typedef vector<pll> vpll; // on the right side
typedef vector<bool> vb;
typedef vector<char> vc;

ll n,d,m;
vector<vll> requests;

bool f(ll machines) {
    ll cur_day=1, mach_used=0;
    
    FOR(1, n + 1) {
        if(i > cur_day) {
            cur_day=i;
            mach_used=0;
        }
        if(!requests[i].size()) continue;
        ll amt_days=ceil(requests[i].size() * 1.0f / machines) - 1;
        mach_used += requests[i].size() - amt_days * machines;
        if(mach_used > machines) {
            mach_used -= machines;
            amt_days++;
        }
        cur_day += amt_days;
        // cout << i << ": "<< cur_day << " " << mach_used << endl;
        if(cur_day - i > d || cur_day > n) return false;
        
    }
    return true;
}

int main() {
    fast

    cin >> n >> d >> m;
    requests.resize(n + 1);
    FOR(1, m+1) {
        ll req;
        cin >> req;
        requests[req].push_back(i);
    }
    ll lb=1, upb=m;
    
    while(lb < upb) {
        ll mid=(upb + lb)/2;
        // cout << "mid :" << mid << endl;
        if(f(mid)) upb=mid;
        else lb=mid+1;
    }
    cout << upb << endl;
    
    ll left=upb, cur_day=1;
    
    FOR(1, n+1) {
        while(i > cur_day) {
            left=upb;
            cur_day++;
            cout << 0 << endl;
            // cout << 1 << " " << cur_day << endl;
        }
        for(auto x : requests[i]) {
            cout << x << " ";
            left--;
            if(!left) {
                cur_day++;
                left=upb;
                cout << 0 << endl;
                // cout << "2" << " " << cur_day<< endl;
            }
        }
    }
    while(cur_day <= n) {
        cout << 0 << endl;
        cur_day++;
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	2516 KB	Output is correct
2	Correct	27 ms	2520 KB	Output is correct
3	Correct	28 ms	2516 KB	Output is correct
4	Correct	21 ms	2516 KB	Output is correct
5	Correct	21 ms	2516 KB	Output is correct
6	Correct	21 ms	2520 KB	Output is correct
7	Correct	22 ms	2516 KB	Output is correct
8	Correct	21 ms	2520 KB	Output is correct
9	Correct	124 ms	4944 KB	Output is correct
10	Correct	119 ms	4984 KB	Output is correct
11	Correct	13 ms	2448 KB	Output is correct
12	Correct	23 ms	4488 KB	Output is correct
13	Correct	34 ms	7764 KB	Output is correct
14	Correct	69 ms	10316 KB	Output is correct
15	Correct	54 ms	11600 KB	Output is correct
16	Correct	90 ms	15184 KB	Output is correct
17	Correct	115 ms	18832 KB	Output is correct
18	Correct	96 ms	18056 KB	Output is correct
19	Correct	204 ms	21328 KB	Output is correct
20	Correct	103 ms	18768 KB	Output is correct