Submission #207136

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
207136	2020-03-06T14:42:08 Z	zvonimir11	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	649 ms	17032 KB

jobs

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, m, d, a[1000005], 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 = 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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	4332 KB	Output is correct
2	Correct	68 ms	4332 KB	Output is correct
3	Correct	71 ms	4336 KB	Output is correct
4	Correct	69 ms	4336 KB	Output is correct
5	Correct	75 ms	4472 KB	Output is correct
6	Correct	69 ms	4340 KB	Output is correct
7	Correct	71 ms	4464 KB	Output is correct
8	Correct	70 ms	4336 KB	Output is correct
9	Correct	236 ms	4620 KB	Output is correct
10	Correct	256 ms	4472 KB	Output is correct
11	Correct	55 ms	4216 KB	Output is correct
12	Correct	104 ms	5880 KB	Output is correct
13	Correct	147 ms	8056 KB	Output is correct
14	Correct	250 ms	9812 KB	Output is correct
15	Correct	227 ms	11000 KB	Output is correct
16	Correct	342 ms	13304 KB	Output is correct
17	Correct	396 ms	15480 KB	Output is correct
18	Correct	404 ms	15736 KB	Output is correct
19	Correct	649 ms	17032 KB	Output is correct
20	Correct	404 ms	15480 KB	Output is correct