Submission #93995

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
93995	2019-01-14T11:46:13 Z	rkocharyan	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	162 ms	13304 KB

jobs

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;

int n, d, m;
int f[N];
vector <int> g[N];

bool check(int t) {
    deque < pair <int, int> > h;
    for(int i = 1; i <= n; i++) {
        if(f[i]) h.emplace_back(i, f[i]);
        int cur_t = t;
        while(!h.empty() && cur_t) {
            if(i - h[0].first > d) return false;
            int next_t = cur_t;
            next_t -= min(h[0].second, cur_t);
            h[0].second -= min(h[0].second, cur_t);
            cur_t = next_t;
            if(h[0].second == 0) {
                h.pop_front();
            }
        }
    }
    if(h.size()) return false;
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d >> m;
    for(int i = 0; i < m; i++) {
        int x;
        cin >> x;
        f[x]++;
        g[x].push_back(i + 1);
    }
    int low = 1, high = m, best = m;
    while(low <= high) {
        int mid = (low + high) >> 1;
        if(check(mid)) {
            best = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << best << '\n';
    deque < pair <int, int> > h;
    for(int i = 1; i <= n; i++) {
        if(f[i]) h.emplace_back(i, f[i]);
        int cur_t = best;
        while(!h.empty() && cur_t) {
            int next_t = cur_t;
            for(int j = 0; j < min(h[0].second, cur_t); j++) {
                cout << g[h[0].first].back() << ' ';
                g[h[0].first].pop_back();
            }
            next_t -= min(h[0].second, cur_t);
            h[0].second -= min(h[0].second, cur_t);
            cur_t = next_t;
            if(h[0].second == 0) {
                h.pop_front();
            }
        }
        cout << "0\n";
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	3824 KB	Output is correct
2	Correct	18 ms	3832 KB	Output is correct
3	Correct	17 ms	3832 KB	Output is correct
4	Correct	17 ms	3828 KB	Output is correct
5	Correct	17 ms	3828 KB	Output is correct
6	Correct	17 ms	3832 KB	Output is correct
7	Correct	17 ms	3828 KB	Output is correct
8	Correct	17 ms	3828 KB	Output is correct
9	Correct	22 ms	4088 KB	Output is correct
10	Correct	22 ms	4088 KB	Output is correct
11	Correct	20 ms	3832 KB	Output is correct
12	Correct	36 ms	4984 KB	Output is correct
13	Correct	56 ms	6824 KB	Output is correct
14	Correct	95 ms	8056 KB	Output is correct
15	Correct	84 ms	8952 KB	Output is correct
16	Correct	136 ms	10716 KB	Output is correct
17	Correct	154 ms	12644 KB	Output is correct
18	Correct	130 ms	12408 KB	Output is correct
19	Correct	153 ms	13304 KB	Output is correct
20	Correct	162 ms	12536 KB	Output is correct