Submission #592320

#	Time	Username	Problem	Language	Result	Execution time	Memory
592320		54skyxenon	Job Scheduling (CEOI12_jobs)	C++17	90 / 100	290 ms	34304 KiB

jobs

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

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

#define int long long

#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 = 1;

    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;
                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);
    }

    bs(1, m);
}

Compilation message (stderr)

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

• Subtask 1: 90 / 100