oj.uz

답안 #918991

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
918991 2024-01-31T02:23:19 Z niwrad Job Scheduling (CEOI12_jobs) C++17
0 / 100
 183 ms 14536 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++;
                }
            }
            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

# 결과 실행 시간 메모리 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