Submission #1045266

#TimeUsernameProblemLanguageResultExecution timeMemory
1045266NeilPJob Scheduling (CEOI12_jobs)C++14
100 / 100
227 ms15240 KiB
#include <iostream>
#include <vector>
#include <queue>

std::vector<int> jobs[100001];
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;
    d++;
    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;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...