oj.uz

Submission #146258

# Submission time Handle Problem Language Result Execution time Memory
146258 2019-08-23T06:53:26 Z dolphingarlic Job Scheduling (CEOI12_jobs) C++14
80 / 100
 346 ms 34552 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[1000001];

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
80.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 25716 KB Output is correct
2 Correct 59 ms 25720 KB Output is correct
3 Correct 67 ms 25904 KB Output is correct
4 Correct 62 ms 25592 KB Output is correct
5 Correct 59 ms 25652 KB Output is correct
6 Correct 59 ms 25716 KB Output is correct
7 Correct 60 ms 25716 KB Output is correct
8 Correct 66 ms 25652 KB Output is correct
9 Correct 60 ms 25336 KB Output is correct
10 Correct 60 ms 25336 KB Output is correct
11 Correct 57 ms 25084 KB Output is correct
12 Correct 91 ms 26232 KB Output is correct
13 Correct 125 ms 28024 KB Output is correct
14 Correct 180 ms 29632 KB Output is correct
15 Correct 191 ms 30200 KB Output is correct
16 Correct 260 ms 31864 KB Output is correct
17 Runtime error 312 ms 33912 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 303 ms 33804 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 346 ms 34552 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 301 ms 33884 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)