Submission #519367

#	Time	Username	Problem	Language	Result	Execution time	Memory
519367		Ekkorash	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	340 ms	23292 KiB

jobs

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

#define ll unsigned long long

ll N;
ll D;
ll M;
std::vector<std::pair<ll, ll>> JOBS;

bool f(ll x) {
    ll cur_day = 1;
    for (ll i = 0; i < M; i += x) {
        if (cur_day > N)
            return false;
        
        for (ll j = 0; j < x; ++j) {
            if (i + j >= M)
                return true;
            
            if (JOBS[i + j].first + D < cur_day) {
                return false;
            }
        }
        
        ++cur_day;
    }
    
    return true;
}

void printsh(ll x) {
    ll index = 0;
    for (ll i =0; i < N; ++i)
    {
        for (ll j = 0; j < x; ++j) {
            if (index < M) {
                std::cout << JOBS[index++].second << " ";
            }
        }
        std::cout << "0\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    std::cin >> N >> D >> M;
    
    for(ll i = 0; i < M; ++i) {
        ll num;
        std::cin >> num;
        
        JOBS.push_back({num, i + 1 });
    }
    
    std::sort(JOBS.begin(), JOBS.end());
    
    ll l = 0;
    ll r = 1e15;
    
    while(l < r) {
        ll mid = l + (r - l)/2;
        
        if (f(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    
    std::cout << l << "\n";
    printsh(l);
    
	return 0;
}

• Subtask 1: 55 / 100