oj.uz

Submission #918988

# Submission time Handle Problem Language Result Execution time Memory
918988 2024-01-31T02:19:00 Z niwrad Job Scheduling (CEOI12_jobs) C++
0 / 100
 188 ms 22456 KB 
#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 (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);
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 2904 KB Execution killed with signal 11
2 Runtime error 13 ms 2888 KB Execution killed with signal 11
3 Runtime error 14 ms 2908 KB Execution killed with signal 11
4 Runtime error 14 ms 2908 KB Execution killed with signal 11
5 Runtime error 14 ms 2904 KB Execution killed with signal 11
6 Runtime error 14 ms 2856 KB Execution killed with signal 11
7 Runtime error 14 ms 2908 KB Execution killed with signal 11
8 Runtime error 14 ms 3104 KB Execution killed with signal 11
9 Runtime error 29 ms 4304 KB Execution killed with signal 11
10 Runtime error 22 ms 4296 KB Execution killed with signal 11
11 Runtime error 21 ms 2800 KB Execution killed with signal 11
12 Runtime error 40 ms 4948 KB Execution killed with signal 11
13 Runtime error 62 ms 7140 KB Execution killed with signal 11
14 Runtime error 84 ms 9808 KB Execution killed with signal 11
15 Runtime error 101 ms 11856 KB Execution killed with signal 11
16 Runtime error 125 ms 14364 KB Execution killed with signal 11
17 Runtime error 147 ms 16468 KB Execution killed with signal 11
18 Runtime error 171 ms 18956 KB Execution killed with signal 11
19 Runtime error 188 ms 22456 KB Execution killed with signal 11
20 Runtime error 149 ms 16672 KB Execution killed with signal 11