Submission #94932

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
94932	2019-01-25T09:53:13 Z	popovicirobert	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	239 ms	16988 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++;
        for(int i = pos; i < min(m + 1, pos + len); i++) {
            if(cnt - arr[i].first > d) {
                return 0;
            }
        }
        pos += len;
    }
    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;
    for(i = 1; i <= n; i++) {
        for(int j = pos; j < min(m + 1, pos + res); j++) {
            cout << arr[j].second << " ";
        }
        cout << "0\n";
        pos += res;
    }
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	18 ms	2040 KB	Output isn't correct
2	Incorrect	18 ms	2040 KB	Output isn't correct
3	Incorrect	18 ms	2040 KB	Output isn't correct
4	Incorrect	18 ms	2040 KB	Output isn't correct
5	Incorrect	18 ms	2040 KB	Output isn't correct
6	Incorrect	18 ms	2040 KB	Output isn't correct
7	Incorrect	18 ms	2040 KB	Output isn't correct
8	Incorrect	19 ms	2040 KB	Output isn't correct
9	Correct	27 ms	2168 KB	Output is correct
10	Correct	28 ms	2168 KB	Output is correct
11	Correct	26 ms	2168 KB	Output is correct
12	Correct	51 ms	3960 KB	Output is correct
13	Correct	76 ms	5716 KB	Output is correct
14	Correct	107 ms	8140 KB	Output is correct
15	Incorrect	126 ms	9608 KB	Output isn't correct
16	Correct	160 ms	11896 KB	Output is correct
17	Correct	194 ms	13816 KB	Output is correct
18	Correct	213 ms	15072 KB	Output is correct
19	Correct	239 ms	16988 KB	Output is correct
20	Correct	181 ms	13816 KB	Output is correct