답안 #93995

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93995 2019-01-14T11:46:13 Z rkocharyan Job Scheduling (CEOI12_jobs) C++14
100 / 100
162 ms 13304 KB
#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;
}
# 결과 실행 시간 메모리 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