Submission #918991

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
918991	2024-01-31T02:23:19 Z	niwrad	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	183 ms	14536 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 (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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	14 ms	1892 KB	Output isn't correct
2	Incorrect	14 ms	1880 KB	Output isn't correct
3	Incorrect	13 ms	1880 KB	Output isn't correct
4	Incorrect	14 ms	1880 KB	Output isn't correct
5	Incorrect	14 ms	1880 KB	Output isn't correct
6	Incorrect	14 ms	1880 KB	Output isn't correct
7	Incorrect	13 ms	1880 KB	Output isn't correct
8	Incorrect	13 ms	1880 KB	Output isn't correct
9	Incorrect	28 ms	2760 KB	Output isn't correct
10	Incorrect	27 ms	2760 KB	Output isn't correct
11	Incorrect	18 ms	1624 KB	Output isn't correct
12	Incorrect	39 ms	3160 KB	Output isn't correct
13	Incorrect	58 ms	4688 KB	Output isn't correct
14	Incorrect	80 ms	6224 KB	Output isn't correct
15	Incorrect	95 ms	7760 KB	Output isn't correct
16	Incorrect	122 ms	9296 KB	Output isn't correct
17	Incorrect	140 ms	10580 KB	Output isn't correct
18	Incorrect	158 ms	12084 KB	Output isn't correct
19	Incorrect	183 ms	14536 KB	Output isn't correct
20	Incorrect	140 ms	10832 KB	Output isn't correct