oj.uz

답안 #106641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106641 2019-04-19T10:51:42 Z naoai Job Scheduling (CEOI12_jobs) C++14
100 / 100
 487 ms 20700 KB 
#include <bits/stdc++.h>

using namespace std;

#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");

const int mmax = 1e6 + 5;

int n, d, m;
int a[mmax + 1];
pair<int, int> v[mmax + 1];

bool check (int val) {
    int i = 1;
    for (int z = 1; z <= n; ++ z) {
        int aux = i;
        for (int j = i; j < i + val && a[j] <= z && j <= m; ++ j, ++ aux) {
            if (a[j] + d < z)
                return 0;
        }
        i = aux;
    }

    return 1;
}

int main() {
   // ios::sync_with_stdio(0); cin.tie(nullptr);
    cin >> n >> d >> m;

    for (int i = 1; i <= m; ++ i) {
        int x;
        cin >> x;
        a[i] = x;
        v[i] = {x, i};
    }

    int n2 = 1;
    for (n2 = 1; (n2 << 1) <= m; n2 <<= 1) {
    }

    sort(a + 1, a + m + 1);

    int ans = m;
    for (int step = n2; step > 0; step >>= 1) {
        if (ans - step > 0 && check(ans - step)) {
            ans -= step;
        }
    }

    sort(v + 1, v + m + 1);

    cout << ans << "\n";

    int i = 1;
    for (int z = 1; z <= n; ++ z) {
        int aux = i;
        for (int j = i; j < i + ans && a[j] <= z && j <= m; ++ j, ++ aux) {
            cout << v[j].second << " ";
        }

        i = aux;
        cout << "0\n";
    }

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 2424 KB Output is correct
2 Correct 56 ms 2424 KB Output is correct
3 Correct 53 ms 2548 KB Output is correct
4 Correct 49 ms 2424 KB Output is correct
5 Correct 49 ms 2424 KB Output is correct
6 Correct 51 ms 2424 KB Output is correct
7 Correct 36 ms 2424 KB Output is correct
8 Correct 68 ms 2440 KB Output is correct
9 Correct 45 ms 2580 KB Output is correct
10 Correct 79 ms 2552 KB Output is correct
11 Correct 60 ms 2472 KB Output is correct
12 Correct 133 ms 4688 KB Output is correct
13 Correct 155 ms 7012 KB Output is correct
14 Correct 241 ms 9720 KB Output is correct
15 Correct 257 ms 11640 KB Output is correct
16 Correct 371 ms 14396 KB Output is correct
17 Correct 405 ms 16612 KB Output is correct
18 Correct 470 ms 18296 KB Output is correct
19 Correct 487 ms 20700 KB Output is correct
20 Correct 454 ms 16632 KB Output is correct