제출 #706116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706116		justinhall363	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	538 ms	20084 KiB

jobs

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

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

bool can(int m){ //can i make all requests with m machines
    days = v2d(N);
    int day = 0, m_i = 0;
    FOR(i, M){
        if(day >= N) return false; //company shuts down
        if(day+1 > reqs[i].r + D) return false;
        days[day].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 ---++
    int lo = 1, hi = 1e6;
    while(lo != hi){
        int mid = (lo+hi)/2;
        if(can(mid)) hi = mid;
        else lo = mid+1;
    }
    
    //print answer
    can(lo);
    cout<<lo<<endl;
    FOR(i, N){
        for(int r : days[i]) cout<<r<<" ";
        cout<<0<<endl;
    }
}

• Subtask 1: 55 / 100