Submission #519350

#	Time	Username	Problem	Language	Result	Execution time	Memory
519350		Ekkorash	Job Scheduling (CEOI12_jobs)	C++17	30 / 100	333 ms	24380 KiB

jobs

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

#define ll 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) {
        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;
}

bool printsh(ll x) {
    int 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";
    }
    
    return true;
}

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(r - l > 1) {
        ll mid = (l + r)/2;
        
        if (f(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    
    std::cout << r << "\n";
    printsh(r);
    
	return 0;
}

• Subtask 1: 30 / 100