Submission #733416

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
733416	2023-04-30T16:42:45 Z	jared	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	396 ms	20168 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	2532 KB	Output is correct
2	Correct	43 ms	2588 KB	Output is correct
3	Correct	33 ms	2532 KB	Output is correct
4	Correct	41 ms	2600 KB	Output is correct
5	Correct	31 ms	2512 KB	Output is correct
6	Correct	33 ms	2512 KB	Output is correct
7	Correct	34 ms	2552 KB	Output is correct
8	Correct	37 ms	2560 KB	Output is correct
9	Correct	150 ms	4792 KB	Output is correct
10	Correct	153 ms	4916 KB	Output is correct
11	Correct	36 ms	2152 KB	Output is correct
12	Correct	69 ms	4196 KB	Output is correct
13	Correct	92 ms	6584 KB	Output is correct
14	Correct	140 ms	9004 KB	Output is correct
15	Correct	163 ms	9672 KB	Output is correct
16	Correct	188 ms	11936 KB	Output is correct
17	Correct	235 ms	15932 KB	Output is correct
18	Correct	246 ms	16436 KB	Output is correct
19	Correct	396 ms	20168 KB	Output is correct
20	Correct	206 ms	15932 KB	Output is correct