Submission #848039

#	Time	Username	Problem	Language	Result	Execution time	Memory
848039		daoda	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	204 ms	21328 KiB

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 / 100