Submission #592332

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
592332	2022-07-08T23:43:07 Z	54skyxenon	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	338 ms	24424 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 {
            while (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";
        }
    }
}

int main() {
    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	30 ms	4924 KB	Output is correct
2	Correct	38 ms	5008 KB	Output is correct
3	Correct	37 ms	4904 KB	Output is correct
4	Correct	31 ms	4980 KB	Output is correct
5	Correct	30 ms	4932 KB	Output is correct
6	Correct	31 ms	4988 KB	Output is correct
7	Correct	30 ms	4984 KB	Output is correct
8	Correct	32 ms	4980 KB	Output is correct
9	Correct	31 ms	5416 KB	Output is correct
10	Correct	30 ms	5212 KB	Output is correct
11	Correct	35 ms	4600 KB	Output is correct
12	Correct	72 ms	6576 KB	Output is correct
13	Correct	101 ms	10612 KB	Output is correct
14	Correct	156 ms	13420 KB	Output is correct
15	Correct	165 ms	15780 KB	Output is correct
16	Correct	242 ms	17904 KB	Output is correct
17	Correct	298 ms	18336 KB	Output is correct
18	Correct	290 ms	24128 KB	Output is correct
19	Correct	338 ms	24424 KB	Output is correct
20	Correct	307 ms	18392 KB	Output is correct