Submission #592330

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
592330	2022-07-08T23:40:50 Z	54skyxenon	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	210 ms	24304 KB

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) {
            leftover = mid;
            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);
}

Compilation message

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	5004 KB	Output is correct
2	Correct	19 ms	5024 KB	Output is correct
3	Correct	20 ms	5020 KB	Output is correct
4	Correct	20 ms	5052 KB	Output is correct
5	Correct	20 ms	4984 KB	Output is correct
6	Correct	19 ms	4940 KB	Output is correct
7	Correct	20 ms	4924 KB	Output is correct
8	Correct	21 ms	5064 KB	Output is correct
9	Correct	20 ms	5452 KB	Output is correct
10	Correct	20 ms	5304 KB	Output is correct
11	Correct	28 ms	4748 KB	Output is correct
12	Correct	41 ms	6648 KB	Output is correct
13	Correct	54 ms	10680 KB	Output is correct
14	Correct	97 ms	13580 KB	Output is correct
15	Correct	99 ms	15744 KB	Output is correct
16	Correct	136 ms	18036 KB	Output is correct
17	Correct	210 ms	18316 KB	Output is correct
18	Correct	161 ms	24248 KB	Output is correct
19	Correct	177 ms	24304 KB	Output is correct
20	Correct	196 ms	18392 KB	Output is correct