Submission #733416

#	Time	Username	Problem	Language	Result	Execution time	Memory
733416		jared	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	396 ms	20168 KiB

jobs

#include <bits/stdc++.h>

#ifdef LOCAL_TEST

#include "debugging.h"

#endif

using namespace std;

void setio(string filename) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (getenv("stdio")) filename = "";
    else if (getenv("local_test")) filename = "test";

    if (!filename.empty()) {
        freopen((filename + ".in").c_str(), "r", stdin);
        freopen((filename + ".out").c_str(), "w", stdout);
    }
}

vector<vector<int>> days;

bool ok(vector<pair<int, int>> &x, int n, int d, int target, bool out) {
    int ptr = 0;
    for (int day = 1; day <= n; day++) {
        int daily_cnt = target;
        while (daily_cnt--) {
            if (ptr >= x.size()) break;
            if (x[ptr].first > day) break;
            if (day - x[ptr].first > d) return false;
            if (out) days[day - 1].push_back(x[ptr].second);
            ptr++;
        }
    }
    return ptr >= x.size();
}

int main() {
    setio("");

    int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> x;
    for (int i = 1; i <= m; i++) {
        int tmp;
        cin >> tmp;
        x.emplace_back(tmp, i);
    }
    sort(x.begin(), x.end());

    int l = 1, r = m;
    while (l < r) {
        int mid = l + (r - l) / 2;

        if (ok(x, n, d, mid, false)) r = mid;
        else l = mid + 1;
    }

    cout << l << endl;
    days.resize(n);
    ok(x, n, d, l, true);
    for (auto &day: days) {
        for (int id: day)
            cout << id << ' ';
        cout << 0 << endl;
    }
}

Compilation message (stderr)

jobs.cpp: In function 'bool ok(std::vector<std::pair<int, int> >&, int, int, int, bool)':
jobs.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             if (ptr >= x.size()) break;
      |                 ~~~~^~~~~~~~~~~
jobs.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     return ptr >= x.size();
      |            ~~~~^~~~~~~~~~~
jobs.cpp: In function 'void setio(std::string)':
jobs.cpp:19:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |         freopen((filename + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen((filename + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100