oj.uz

답안 #918986

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
918986 2024-01-31T02:15:29 Z niwrad Job Scheduling (CEOI12_jobs) C++17
0 / 100
 192 ms 26076 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 3160 KB Execution killed with signal 11
2 Runtime error 15 ms 3160 KB Execution killed with signal 11
3 Runtime error 14 ms 3152 KB Execution killed with signal 11
4 Runtime error 14 ms 3160 KB Execution killed with signal 11
5 Runtime error 14 ms 3160 KB Execution killed with signal 11
6 Runtime error 14 ms 3360 KB Execution killed with signal 11
7 Runtime error 14 ms 3152 KB Execution killed with signal 11
8 Runtime error 15 ms 3080 KB Execution killed with signal 11
9 Runtime error 22 ms 4444 KB Execution killed with signal 11
10 Runtime error 22 ms 4552 KB Execution killed with signal 11
11 Runtime error 22 ms 3172 KB Execution killed with signal 11
12 Runtime error 43 ms 5712 KB Execution killed with signal 11
13 Runtime error 61 ms 8272 KB Execution killed with signal 11
14 Runtime error 85 ms 11548 KB Execution killed with signal 11
15 Runtime error 102 ms 13976 KB Execution killed with signal 11
16 Runtime error 127 ms 17232 KB Execution killed with signal 11
17 Runtime error 153 ms 20020 KB Execution killed with signal 11
18 Runtime error 167 ms 21780 KB Execution killed with signal 11
19 Runtime error 192 ms 26076 KB Execution killed with signal 11
20 Runtime error 148 ms 20048 KB Execution killed with signal 11