oj.uz

Submission #207135

# Submission time Handle Problem Language Result Execution time Memory
207135 2020-03-06T14:41:28 Z zvonimir11 Job Scheduling (CEOI12_jobs) C++17
75 / 100
 648 ms 38240 KB 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, m, d, a[1000005], b[1000005];
vector<int> dn[1000005];

bool f(int x, bool is) {
    queue<int> p;
    for(int i = 1; i <= n; ++i) {
        int o = x;
        while(!p.empty() && o > 0) {
            if(i - p.front() > d)
                return 0;
            --o;
            if(is)
                cout << dn[p.front()].back() << " ", dn[p.front()].pop_back();
            p.pop();
        }
        for(int j = 0; j < b[i]; ++j) {
            if(o > 0) {
                --o;
                if(is)
                    cout << dn[i].back() << " ", dn[i].pop_back();
                continue;
            }
            p.push(i);
        }
        if(is)
            cout << 0 << endl;
    }
    if(p.size() > 0)
        return 0;
    return 1;
}

int main() {
    cin >> n >> d >> m;
    for(int i = 0; i < m; ++i)
        cin >> a[i], ++b[a[i]], dn[a[i]].push_back(i + 1);

    int lo = 1, hi = 1000005;
    while(lo < hi) {
        int md = (hi + lo) / 2;
        if(f(md, 0))
            hi = md;
        else
            lo = md + 1;
    }
    cout << lo << endl;
    f(lo, 1);
    return 0;
}

Subtask #1
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 25452 KB Output is correct
2 Correct 87 ms 25456 KB Output is correct
3 Correct 85 ms 25456 KB Output is correct
4 Correct 85 ms 25584 KB Output is correct
5 Correct 82 ms 25456 KB Output is correct
6 Correct 86 ms 25552 KB Output is correct
7 Correct 83 ms 25456 KB Output is correct
8 Correct 85 ms 25584 KB Output is correct
9 Correct 264 ms 25748 KB Output is correct
10 Correct 262 ms 25720 KB Output is correct
11 Correct 68 ms 25464 KB Output is correct
12 Correct 118 ms 27000 KB Output is correct
13 Correct 160 ms 29176 KB Output is correct
14 Correct 265 ms 30932 KB Output is correct
15 Correct 243 ms 32120 KB Output is correct
16 Runtime error 353 ms 34424 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
17 Runtime error 428 ms 36600 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
18 Runtime error 417 ms 36860 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
19 Runtime error 648 ms 38240 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
20 Runtime error 415 ms 36600 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)