oj.uz

Submission #207129

# Submission time Handle Problem Language Result Execution time Memory
207129 2020-03-06T14:36:42 Z zvonimir11 Job Scheduling (CEOI12_jobs) C++17
55 / 100
 251 ms 5364 KB 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

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

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 = 100005;
    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
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4720 KB Output is correct
2 Correct 70 ms 4724 KB Output is correct
3 Correct 70 ms 4744 KB Output is correct
4 Correct 70 ms 4720 KB Output is correct
5 Correct 70 ms 4716 KB Output is correct
6 Correct 69 ms 4720 KB Output is correct
7 Correct 71 ms 4852 KB Output is correct
8 Correct 71 ms 4720 KB Output is correct
9 Correct 240 ms 4728 KB Output is correct
10 Correct 244 ms 4856 KB Output is correct
11 Correct 56 ms 4600 KB Output is correct
12 Incorrect 56 ms 4856 KB Output isn't correct
13 Incorrect 58 ms 4856 KB Output isn't correct
14 Incorrect 82 ms 5240 KB Output isn't correct
15 Incorrect 53 ms 4856 KB Output isn't correct
16 Incorrect 82 ms 5240 KB Output isn't correct
17 Incorrect 86 ms 5364 KB Output isn't correct
18 Incorrect 80 ms 5048 KB Output isn't correct
19 Incorrect 251 ms 5356 KB Output isn't correct
20 Incorrect 83 ms 5336 KB Output isn't correct