oj.uz

Submission #146259

# Submission time Handle Problem Language Result Execution time Memory
146259 2019-08-23T06:54:13 Z dolphingarlic Job Scheduling (CEOI12_jobs) C++14
100 / 100
 349 ms 13660 KB 
#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;

vector<int> a[100001];

bool check(int machines, int days, int jobs, int delay, bool output) {
    queue<pair<int, int>> pending;
    FOR(i, 1, days + 1) {
        for (int j : a[i]) pending.push({i, j});

        for (int j = 0; j < machines && pending.size(); j++) {
            if (i - pending.front().first > delay) return false;
            if (output) cout << pending.front().second << ' ';
            pending.pop();
        }

        if (output) cout << "0\n";
    }
    return true;
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    int n, d, m;
    cin >> n >> d >> m;
    FOR(i, 1, m + 1) {
        int x;
        cin >> x;
        a[x].push_back(i);
    }

    int l = 1, r = m;
    while (l != r) {
        int mid = (l + r) / 2;
        if (check(mid, n, m, d, false)) r = mid;
        else l = mid + 1;
    }

    cout << l << '\n';
    check(l, n, m, d, true);
    return 0;
}

Compilation message

jobs.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 4592 KB Output is correct
2 Correct 42 ms 4596 KB Output is correct
3 Correct 41 ms 4468 KB Output is correct
4 Correct 41 ms 4504 KB Output is correct
5 Correct 41 ms 4532 KB Output is correct
6 Correct 40 ms 4568 KB Output is correct
7 Correct 40 ms 4468 KB Output is correct
8 Correct 41 ms 4584 KB Output is correct
9 Correct 40 ms 4088 KB Output is correct
10 Correct 41 ms 4088 KB Output is correct
11 Correct 37 ms 3832 KB Output is correct
12 Correct 71 ms 5112 KB Output is correct
13 Correct 106 ms 6904 KB Output is correct
14 Correct 167 ms 8468 KB Output is correct
15 Correct 173 ms 9080 KB Output is correct
16 Correct 249 ms 10784 KB Output is correct
17 Correct 274 ms 12792 KB Output is correct
18 Correct 287 ms 12704 KB Output is correct
19 Correct 349 ms 13660 KB Output is correct
20 Correct 295 ms 12760 KB Output is correct