Submission #1045196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045196		NeilP	Job Scheduling (CEOI12_jobs)	C++14	30 / 100	230 ms	16980 KiB

jobs

#include <iostream>
#include <vector>
#include <queue>

std::vector<int> jobs[100000];
int n, m, d;

bool check(int a){
    int max_queue = a * d;
    int len = 0;
    for(int i = 0; i < n; i++){
        len += jobs[i].size();
        if(len > max_queue) return false;
        len -= a;
        if(len < 0) len = 0;
    }
    return true;
}

int main(){
    std::cin >> n >> d >> m;
    for(int i = 0; i < m; i++){
        int a;
        std::cin >> a;
        a--;
        jobs[a].push_back(i+1);
    }
    int lower = 0;
    int higher = m;
    while(higher > lower + 1){
        int mid = (higher + lower) / 2;
        if(check(mid)) higher = mid;
        else lower = mid;
    }
    std::cout << higher << std::endl;
    std::queue<int> jbs;
    for(int i = 0; i < n; i++){
        for(int a: jobs[i]){
            jbs.push(a);
        }
        for(int j = 0; j < higher; j++){
            if(jbs.empty()) break;
            std::cout << jbs.front() << " ";
            jbs.pop();
        }
        std::cout << 0 << std::endl;
    }
    return 0;
}

• Subtask 1: 30 / 100