제출 #592329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
592329		54skyxenon	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	177 ms	20588 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);
vector<pair<int, vector<int>>> compressed;

int n, d, m;

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

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

    vector<int> curr_day_schedule;

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

        if (leftover >= requests_here[i].second.size()) {
            curr_day_schedule.insert(curr_day_schedule.end(), requests_here[i].second.begin(), requests_here[i].second.end());
            leftover -= requests_here[i].second.size();
            requests_here[i].second.clear();
        }
        else {
            for (int _ = 0; _ < leftover; _++) {
                curr_day_schedule.push_back(requests_here[i].second.back());
                requests_here[i].second.pop_back();
            }
            schedule.push_back(curr_day_schedule);
            curr_day_schedule.clear();
            leftover = mid;
            curr_day += 1;
            i--;
        }
        i++;
    }
    
    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;
                if (req_id > 0) {
                    cout << " ";
                }
            }
            cout << "\n";
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> d >> m;

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

    for (int day = 1; day <= n; day++) {
        if (requests_by_day[day].size() > 0) {
            compressed.push_back(make_pair(day, vector<int>(requests_by_day[day])));
        }
    }
    requests_by_day.clear();

    bs(1, m);
}

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

jobs.cpp: In function 'std::vector<std::vector<int> > ok(int)':
jobs.cpp:25:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     while (i < requests_here.size()) {
      |            ~~^~~~~~~~~~~~~~~~~~~~~~
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].second.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: 90 / 100