Submission #706119

#	Time	Username	Problem	Language	Result	Execution time	Memory
706119		justinhall363	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	536 ms	33532 KiB

jobs

#include <iostream>
#include <vector>
#include <algorithm>

using namespace::std;
typedef long long ll;
#define FOR(i, b) for(ll i = 0; i < b; i++)
typedef vector<ll> vint;
typedef vector<vint> v2d;
struct req{ ll r, id;
    bool operator<(const req& o)const{ return r < o.r; }};
ll N, D, M;
vector<req> reqs;
v2d days;

bool can(ll m){ //can i make all requests with m machines
    days = v2d(N);
    ll day = 1, m_i = 0;
    FOR(i, M){
        day = max(day, reqs[i].r); //cant start till on submission date
        if(day > reqs[i].r + D) return false; //done after delay

        days[day-1].push_back(reqs[i].id);
        m_i++; //used this machine
        if(m_i == m){ day++; m_i = 0; } //all machines that day used up
    }
    return true;
}

int main() {
    //freopen("jobs.in", "r", stdin);
    //freopen("jobs.out", "w", stdout);
    cin>>N>>D>>M;
    reqs.resize(M);
    FOR(i, M) { cin>>reqs[i].r; reqs[i].id = i+1; }
    sort(reqs.begin(), reqs.end());

    //binary search on # of machines ---++
    ll lo = 1, hi = 1e6;
    while(lo != hi){
        ll mid = (lo+hi)/2;
        if(can(mid)) hi = mid;
        else lo = mid+1;
    }
    
    //print answer
    can(lo);
    cout<<lo<<endl;
    FOR(i, N){
        for(ll r : days[i]) cout<<r<<" ";
        cout<<0<<endl;
    }
}

• Subtask 1: 90 / 100