Submission #918992

#	Time	Username	Problem	Language	Result	Execution time	Memory
918992		niwrad	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	187 ms	14904 KiB

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 (i <= n && 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: 100 / 100