제출 #706120

#제출 시각아이디문제언어결과실행 시간메모리
706120justinhall363Job Scheduling (CEOI12_jobs)C++14
100 / 100
509 ms20144 KiB
#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 = 1, m_i = 0;
    FOR(i, M){
        if(reqs[i].r > day){ day = reqs[i].r; m_i = 0;} //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() {
    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;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...