제출 #592314

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
592314		54skyxenon	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	383 ms	26308 KiB

jobs

// https://oj.uz/problem/view/CEOI12_jobs

#include <bits/stdc++.h>
using namespace std;

#define maxN 100000
#define maxM 1000000

vector<vector<int>> requests_by_day(maxN + 1);

int n, d, m;

// does `mid` number of machines work?
vector<vector<int>> ok(int mid) {
    
    vector<vector<int>> requests_here = requests_by_day;

    vector<vector<int>> schedule;
    int leftover = mid;
    int curr_day = 1;
    int i = 0;

    vector<int> curr_day_schedule;

    while (i <= n) {
        if (curr_day < i) {
            curr_day++;
            continue;
        }
        
        if (curr_day - i > d && requests_here[i].size() > 0) {
            return {};
        }

        if (leftover >= requests_here[i].size()) {
            curr_day_schedule.insert(curr_day_schedule.end(), requests_here[i].begin(), requests_here[i].end());
            leftover -= requests_here[i].size();
            requests_here[i].clear();
        }
        else {
            while (leftover--) {
                curr_day_schedule.push_back(requests_here[i].back());
                requests_here[i].pop_back();
            }
            schedule.push_back(curr_day_schedule);
            curr_day_schedule.clear();
            leftover = mid;
            curr_day += 1;
            i -= 1;
        }
        i += 1;
    }
    
    if (curr_day_schedule.size() > 0) {
        schedule.push_back(curr_day_schedule);
    }

    return schedule;
}

// O(log M * (N + M))
void bs(int lo, int hi) {
    hi++;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (ok(mid).size() > 0) {
            hi = mid;
        }
        else {
            lo = mid + 1;
        }
    }

    cout << lo << "\n";

    vector<vector<int>> ans = ok(lo);
    for (int i = 0; i < n; i++) {
        if (i >= ans.size()) {
            cout << "0\n";
        }
        else {
            ans[i].push_back(0);
            for (int req_id : ans[i]) {
                cout << req_id << " ";
            }
            cout << "\n";
        }
    }
}

int main() {
    cin >> n >> d >> m;

    for (int i = 1; i <= m; i++) {
        int day; cin >> day;
        requests_by_day[day].push_back(i);
    }

    bs(1, m);
}

컴파일 시 표준 에러 (stderr) 메시지

jobs.cpp: In function 'std::vector<std::vector<int> > ok(int)':
jobs.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if (leftover >= requests_here[i].size()) {
      |             ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp: In function 'void bs(int, int)':
jobs.cpp:78:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         if (i >= ans.size()) {
      |             ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 100