Submission #918989

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
918989	2024-01-31T02:20:29 Z	niwrad	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	190 ms	14532 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++;
                }
            }
        }
    }
    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

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	1880 KB	Output is correct
2	Correct	13 ms	1880 KB	Output is correct
3	Correct	13 ms	1880 KB	Output is correct
4	Correct	14 ms	2036 KB	Output is correct
5	Correct	15 ms	1880 KB	Output is correct
6	Correct	13 ms	1880 KB	Output is correct
7	Correct	14 ms	1880 KB	Output is correct
8	Correct	13 ms	1880 KB	Output is correct
9	Correct	25 ms	2760 KB	Output is correct
10	Correct	26 ms	2756 KB	Output is correct
11	Correct	19 ms	1624 KB	Output is correct
12	Incorrect	39 ms	3140 KB	Output isn't correct
13	Correct	59 ms	4688 KB	Output is correct
14	Incorrect	86 ms	6224 KB	Output isn't correct
15	Correct	99 ms	7764 KB	Output is correct
16	Correct	126 ms	9296 KB	Output is correct
17	Correct	143 ms	10832 KB	Output is correct
18	Correct	170 ms	12108 KB	Output is correct
19	Correct	190 ms	14532 KB	Output is correct
20	Correct	142 ms	10832 KB	Output is correct