oj.uz

Submission #706120

# Submission time Handle Problem Language Result Execution time Memory
706120 2023-03-05T23:45:01 Z justinhall363 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 509 ms 20144 KB 
#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;
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2660 KB Output is correct
2 Correct 55 ms 2644 KB Output is correct
3 Correct 49 ms 2648 KB Output is correct
4 Correct 49 ms 2628 KB Output is correct
5 Correct 51 ms 2660 KB Output is correct
6 Correct 50 ms 2680 KB Output is correct
7 Correct 55 ms 2820 KB Output is correct
8 Correct 49 ms 2740 KB Output is correct
9 Correct 160 ms 8680 KB Output is correct
10 Correct 162 ms 8796 KB Output is correct
11 Correct 49 ms 2188 KB Output is correct
12 Correct 95 ms 4164 KB Output is correct
13 Correct 133 ms 6620 KB Output is correct
14 Correct 232 ms 9016 KB Output is correct
15 Correct 220 ms 9652 KB Output is correct
16 Correct 312 ms 12004 KB Output is correct
17 Correct 413 ms 16160 KB Output is correct
18 Correct 362 ms 16476 KB Output is correct
19 Correct 509 ms 20144 KB Output is correct
20 Correct 420 ms 16212 KB Output is correct