oj.uz

답안 #207130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
207130 2020-03-06T14:37:39 Z zvonimir11 Job Scheduling (CEOI12_jobs) C++17
55 / 100
 256 ms 4728 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 = 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
55.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 4332 KB Output is correct
2 Correct 73 ms 4336 KB Output is correct
3 Correct 70 ms 4332 KB Output is correct
4 Correct 69 ms 4336 KB Output is correct
5 Correct 70 ms 4336 KB Output is correct
6 Correct 71 ms 4336 KB Output is correct
7 Correct 71 ms 4332 KB Output is correct
8 Correct 70 ms 4336 KB Output is correct
9 Correct 245 ms 4472 KB Output is correct
10 Correct 249 ms 4576 KB Output is correct
11 Correct 54 ms 4216 KB Output is correct
12 Incorrect 57 ms 4436 KB Output isn't correct
13 Incorrect 56 ms 4328 KB Output isn't correct
14 Incorrect 84 ms 4600 KB Output isn't correct
15 Incorrect 56 ms 4316 KB Output isn't correct
16 Incorrect 85 ms 4728 KB Output isn't correct
17 Incorrect 86 ms 4728 KB Output isn't correct
18 Incorrect 78 ms 4484 KB Output isn't correct
19 Incorrect 256 ms 4668 KB Output isn't correct
20 Incorrect 83 ms 4600 KB Output isn't correct