Submission #918992

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
918992	2024-01-31T02:24:22 Z	niwrad	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	187 ms	14904 KB

jobs

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <array>
#include <cstdio>
#include <vector>
#include <string>
#include <fstream>
#include <tuple>
#include <numeric>
#include <map>
#include <iomanip>
#include <math.h>
#include <queue>
#include <sstream>
#include <stack>
#include <initializer_list>
#include <functional>
#include <cstring>



std::vector<std::pair<int, int>> jobs;
std::vector<int> days;
int n, d, m;

bool solve(int mid) {
    std::vector<int> ds = days;
    int i = 1;
    for (int day = 1; day <= n; day++) {
        int count = mid;
        if (i < day - d) {
            return false;
        } else {
            while (i <= day && count > 0) {
                int dif = std::min(count, ds[i]);
                count -= dif;
                ds[i] -= dif;
                if (ds[i] == 0) {
                    i++;
                }
            }
            while (i <= n && ds[i] == 0) {
                i++;
            }
        }
    }
    if (i == n + 1) {
        return true;
    } else {
        return false;
    }
}
void print(int r) {
    std::cout << r << "\n";
    int cur = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < r; j++) {
            if (cur < m && jobs[cur].first <= i) {
                std::cout << jobs[cur].second << " ";
                cur++;
            } else {
                break;
            }
        }
        std::cout << 0 << "\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    //freopen("shuffle.in", "r", stdin);
    //freopen("shuffle.out", "w", stdout);
    std::cin >> n >> d >> m;
    jobs.resize(m);
    for (int i = 0; i < m; i++) {
        std::cin >> jobs[i].first;
        jobs[i].second = i + 1;
    }
    std::sort(jobs.begin(), jobs.end());
    days.resize(n + 1);
    for (int i = 0; i < m; i++) {
        days[jobs[i].first]++;
    }
    int l = 0;
    int r = m;
    while (r > l + 1) {
        int mid = (l + r) / 2;
        if (solve(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    print(r);
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	1880 KB	Output is correct
2	Correct	13 ms	1880 KB	Output is correct
3	Correct	14 ms	1880 KB	Output is correct
4	Correct	13 ms	1880 KB	Output is correct
5	Correct	13 ms	2080 KB	Output is correct
6	Correct	13 ms	1880 KB	Output is correct
7	Correct	13 ms	1880 KB	Output is correct
8	Correct	13 ms	1880 KB	Output is correct
9	Correct	25 ms	2768 KB	Output is correct
10	Correct	25 ms	2772 KB	Output is correct
11	Correct	21 ms	1624 KB	Output is correct
12	Correct	39 ms	3312 KB	Output is correct
13	Correct	58 ms	4688 KB	Output is correct
14	Correct	82 ms	6228 KB	Output is correct
15	Correct	96 ms	7708 KB	Output is correct
16	Correct	127 ms	9264 KB	Output is correct
17	Correct	143 ms	10792 KB	Output is correct
18	Correct	162 ms	12152 KB	Output is correct
19	Correct	187 ms	14904 KB	Output is correct
20	Correct	142 ms	10648 KB	Output is correct