Submission #598487

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
598487	2022-07-18T11:58:57 Z	stevancv	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	281 ms	23804 KB

jobs

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e5 + 2;
const int mod = 1e9 + 7;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i].first;
        a[i].first -= 1;
        a[i].second = i + 1;
    }
    vector<int> day(m);
    sort(a.begin(), a.end());
    auto Can = [&] (int mid) {
        for (int i = 0; i < m; i++) day[i] = -1;
        int j = -1;
        for (int i = 0; i < n; i++) {
            int r = j;
            while (r <= min(m - 2, j + mid - 1) && a[r + 1].first <= i) r++;
            for (int o = j + 1; o <= r; o++) {
                day[o] = i;
            }
            j = r;
        }
        for (int i = 0; i < m; i++) {
            if (!(a[i].first <= day[i] && day[i] <= a[i].first + d)) return false;
        }
        return true;
    };
    int l = 1; int r = m - 1; int ans = m;
    while (l <= r) {
        int mid = l + r >> 1;
        if (Can(mid)) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    Can(ans);
    cout << ans << en;
    vector<vector<int>> pos(n);
    for (int i = 0; i < m; i++) pos[day[i]].push_back(a[i].second);
    for (int i = 0; i < n; i++) {
        for (int u : pos[i]) cout << u << sp;
        cout << 0 << en;
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:43:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	2772 KB	Output is correct
2	Correct	19 ms	2876 KB	Output is correct
3	Correct	20 ms	2772 KB	Output is correct
4	Correct	22 ms	2800 KB	Output is correct
5	Correct	20 ms	2784 KB	Output is correct
6	Correct	20 ms	2772 KB	Output is correct
7	Correct	22 ms	2768 KB	Output is correct
8	Correct	20 ms	2780 KB	Output is correct
9	Correct	39 ms	5084 KB	Output is correct
10	Correct	36 ms	5068 KB	Output is correct
11	Correct	27 ms	2508 KB	Output is correct
12	Correct	57 ms	5028 KB	Output is correct
13	Correct	83 ms	7928 KB	Output is correct
14	Correct	117 ms	10700 KB	Output is correct
15	Correct	164 ms	11692 KB	Output is correct
16	Correct	207 ms	14512 KB	Output is correct
17	Correct	216 ms	18764 KB	Output is correct
18	Correct	233 ms	19596 KB	Output is correct
19	Correct	281 ms	23804 KB	Output is correct
20	Correct	216 ms	18720 KB	Output is correct