Submission #470959

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
470959	2021-09-06T11:53:55 Z	XII	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	475 ms	13764 KB

jobs

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "CEOI12_jobs"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

int firstTrue(int lo, int hi, function<bool(int)> f){
    while(lo < hi){
        int mid = lo + (hi - lo) / 2;
        if(f(mid)) hi = mid;
        else lo = mid + 1;
    }
    return hi;
}

int main(){
    IOS;
    Fi();
    int n, d, m; cin >> n >> d >> m;
    vector<int> day(m);
    for(int &x: day) cin >> x;
    vector<int> pos(m); iota(ALL(pos), 0);
    sort(ALL(pos), [&](const int &i, const int &j){
            return day[i] < day[j];
        }
    );

    const auto check = [&](const int &x) -> bool{
        int i = 0;
        FORU(T, 1, n) FOR(j, 0, x) if(i < m && day[pos[i]] <= T){
            if(i < m && day[pos[i++]] + d < T) return false;
        } else break;
        return (i >= m);
    };

    int ans = firstTrue(m / n + (m % n ? 1 : 0), m, check);
    cout << ans << "\n";
    int i = 0;
    FORU(T, 1, n){
        FOR(j, 0, ans) if(i < m && day[pos[i]] <= T){
            if(i < m) cout << pos[i++] + 1 << " ";
        } else break;
        cout << "0\n";
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'void Fi()':
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(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	1612 KB	Output is correct
2	Correct	28 ms	1616 KB	Output is correct
3	Correct	23 ms	1688 KB	Output is correct
4	Correct	32 ms	1604 KB	Output is correct
5	Correct	24 ms	1608 KB	Output is correct
6	Correct	26 ms	1612 KB	Output is correct
7	Correct	25 ms	1660 KB	Output is correct
8	Correct	23 ms	1636 KB	Output is correct
9	Correct	30 ms	1868 KB	Output is correct
10	Correct	31 ms	1820 KB	Output is correct
11	Correct	35 ms	1616 KB	Output is correct
12	Correct	71 ms	3172 KB	Output is correct
13	Correct	106 ms	4568 KB	Output is correct
14	Correct	152 ms	6084 KB	Output is correct
15	Correct	178 ms	7620 KB	Output is correct
16	Correct	238 ms	9100 KB	Output is correct
17	Correct	338 ms	10580 KB	Output is correct
18	Correct	281 ms	12100 KB	Output is correct
19	Correct	475 ms	13764 KB	Output is correct
20	Correct	297 ms	10600 KB	Output is correct