Submission #727834

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
727834	2023-04-21T11:59:35 Z	buffering	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	842 ms	23596 KB

jobs

#include <bits/stdc++.h>
using namespace std;
 
void IO(string s = "")
{
    if (s == "")
    {
        freopen("input.txt", "r", stdin);
        freopen("output 2.txt", "w", stdout);
    }
    if (s != "")
    {
        freopen((s + ".in").c_str(), "r", stdin);
        freopen((s + ".out").c_str(), "w", stdout);
    }
}
bool check(vector<pair<int, int>>& req, int machines, int d, int n, bool print) {
    if (machines < 1) return false;
    vector<vector<int>> days;
    for (int i = 0; i < n; i++) {
        days.push_back({});
    }
    int delay = 0;
 
    int day = 1;
 
    int i = 0;
 
    while (i < req.size() && day < n) {
        if (days[day - 1].size() == machines) {
            day++;
            if (day == n) break;
        }
        if (req[i].first > day) {
            day = req[i].first;
        }
        days[day - 1].push_back(req[i].second);
        delay = max(delay, abs(req[i].first - day));
        i++;
    }
    if (delay > d) return false;
    if (print) {
        for (auto v: days) {
            for (int i = 0; i < v.size(); i++) {
                cout << v[i] << " ";
            }
            cout << 0 << endl;
        }
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    //IO();
 
    int n; int d; int m;
    cin >> n >> d >> m;
 
    vector<pair<int, int>> req(m);
 
    for (int i = 0; i < m; i++) {
        cin >> req[i].first;
        req[i].second = i + 1;
    }
    sort(req.begin(), req.end());
 
    int lo = 1; int hi = 1e9;
 
    while (lo <= hi) {
        int mid = (lo + hi)/2;
        if (check(req, mid, d, n, 0)) {
            if (!check(req, mid - 1, d, n, 0)) {
                cout << mid << endl;
                check(req, mid, d, n, 1);
                break;
            }
            else hi = mid - 1;
        }
        else lo = mid + 1;
    }
 
 
 
}

Compilation message

jobs.cpp: In function 'bool check(std::vector<std::pair<int, int> >&, int, int, int, bool)':
jobs.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while (i < req.size() && day < n) {
      |            ~~^~~~~~~~~~~~
jobs.cpp:30:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |         if (days[day - 1].size() == machines) {
      |             ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
jobs.cpp:44:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for (int i = 0; i < v.size(); i++) {
      |                             ~~^~~~~~~~~~
jobs.cpp: In function 'void IO(std::string)':
jobs.cpp:8:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:9:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |         freopen("output 2.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen((s + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen((s + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	83 ms	2948 KB	Output is correct
2	Correct	80 ms	2956 KB	Output is correct
3	Correct	80 ms	3012 KB	Output is correct
4	Correct	82 ms	3052 KB	Output is correct
5	Correct	84 ms	2992 KB	Output is correct
6	Correct	82 ms	2992 KB	Output is correct
7	Correct	85 ms	3084 KB	Output is correct
8	Correct	84 ms	3020 KB	Output is correct
9	Correct	302 ms	7628 KB	Output is correct
10	Correct	296 ms	7524 KB	Output is correct
11	Correct	81 ms	2536 KB	Output is correct
12	Correct	149 ms	4908 KB	Output is correct
13	Correct	224 ms	7752 KB	Output is correct
14	Correct	375 ms	11112 KB	Output is correct
15	Correct	388 ms	11596 KB	Output is correct
16	Correct	617 ms	15028 KB	Output is correct
17	Correct	644 ms	19556 KB	Output is correct
18	Correct	624 ms	19460 KB	Output is correct
19	Correct	842 ms	23596 KB	Output is correct
20	Correct	646 ms	19420 KB	Output is correct