Submission #519353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
519353	2022-01-26T08:53:39 Z	Ekkorash	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	307 ms	20996 KB

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

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	69 ms	2564 KB	Output isn't correct
2	Incorrect	42 ms	2540 KB	Output isn't correct
3	Incorrect	35 ms	2612 KB	Output isn't correct
4	Incorrect	32 ms	2612 KB	Output isn't correct
5	Incorrect	30 ms	2560 KB	Output isn't correct
6	Incorrect	29 ms	2608 KB	Output isn't correct
7	Incorrect	27 ms	2596 KB	Output isn't correct
8	Incorrect	29 ms	2628 KB	Output isn't correct
9	Correct	257 ms	2828 KB	Output is correct
10	Correct	264 ms	2792 KB	Output is correct
11	Correct	26 ms	2504 KB	Output is correct
12	Correct	55 ms	4820 KB	Output is correct
13	Correct	81 ms	8600 KB	Output is correct
14	Correct	111 ms	9404 KB	Output is correct
15	Incorrect	151 ms	11684 KB	Output isn't correct
16	Correct	176 ms	16832 KB	Output is correct
17	Correct	253 ms	16744 KB	Output is correct
18	Correct	235 ms	18404 KB	Output is correct
19	Correct	307 ms	20996 KB	Output is correct
20	Correct	205 ms	16816 KB	Output is correct