Submission #94933

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
94933	2019-01-25T09:56:15 Z	popovicirobert	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	231 ms	14004 KB

jobs

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXM = (int) 1e6;

pair <int, int> arr[MAXM + 1];

inline bool check(int m, int d, int len) {
    int pos = 1;
    int cnt = 0;
    while(pos <= m) {
        cnt++;
        int i;
        for(i = pos; i < min(m + 1, pos + len) && cnt >= arr[i].first; i++) {
            if(cnt - arr[i].first > d) {
                return 0;
            }
        }
        pos = i;
    }
    return 1;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m, d;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> d >> m;
    for(i = 1; i <= m; i++) {
        cin >> arr[i].first;
        arr[i].second = i;
    }
    sort(arr + 1, arr + m + 1);
    int res = 0;
    for(int step = 1 << 20; step; step >>= 1) {
        if(check(m, d, res + step) == 0) {
            res += step;
        }
    }
    res++;
    cout << res << "\n";
    int pos = 1;
    int cnt = 0;
    for(i = 1; i <= n; i++) {
        int j;
        cnt++;
        for(j = pos; j < min(m + 1, pos + res) && cnt >= arr[j].first; j++) {
            cout << arr[j].second << " ";
        }
        cout << "0\n";
        pos = j;
    }
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	2168 KB	Output is correct
2	Correct	19 ms	2040 KB	Output is correct
3	Correct	19 ms	2040 KB	Output is correct
4	Correct	20 ms	2040 KB	Output is correct
5	Correct	19 ms	2040 KB	Output is correct
6	Correct	19 ms	2040 KB	Output is correct
7	Correct	19 ms	2040 KB	Output is correct
8	Correct	19 ms	2040 KB	Output is correct
9	Correct	28 ms	2168 KB	Output is correct
10	Correct	28 ms	2168 KB	Output is correct
11	Correct	26 ms	2040 KB	Output is correct
12	Correct	51 ms	3704 KB	Output is correct
13	Correct	78 ms	4984 KB	Output is correct
14	Correct	109 ms	6468 KB	Output is correct
15	Correct	210 ms	7876 KB	Output is correct
16	Correct	159 ms	9460 KB	Output is correct
17	Correct	190 ms	10800 KB	Output is correct
18	Correct	208 ms	12536 KB	Output is correct
19	Correct	231 ms	14004 KB	Output is correct
20	Correct	220 ms	10968 KB	Output is correct