답안 #791936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791936 2023-07-24T12:42:10 Z matu Job Scheduling (CEOI12_jobs) C++14
55 / 100
183 ms 14544 KB
#include <bits/stdc++.h>
using namespace std;
const int M = 1e6 + 1;
int n, d, m;
vector<pair<int, int>> v(M);

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> d >> m;
    for(int i = 1; i <= m; i++){
        cin >> v[i].first;
        v[i].second = i;
    }
    sort(v.begin() + 1, v.begin() + 1 + m);
    auto ok =  [&](int nrb){
        vector<int> zd;
        int st = 1, dr = 1;
        for(int i = 1; i <= n && st <= m && dr <= m; i++){
            while(dr <= m && v[dr].first == i){
                dr++;
            }
            dr--;
            st += nrb;
            if(st > m){
                return 1;
            }
            dr = max(dr, st);
            if(v[st].first + d <= i){
                return 0;
            }
        }
        return 1;
    };
    auto pr =  [&](int nrb, int pl){
        vector<int> zd;
        int st = 1, dr = 1;
        for(int i = 1; i <= n; i++){
            while(dr <= m && v[dr].first == i){
                dr++;
            }
            dr--;
            for(int j = st; j < st + nrb; j++){
                if(j > m) break;
                cout << v[j].second << " ";
            }
            cout << 0 << '\n';
            st += nrb;
            dr = max(dr, st);
        }
        return;
    };
    int st = 1, dr = 1e9;
    while(st <= dr){
        int tm = (st + dr) / 2;
        if(ok(tm)){
            dr = tm - 1;
        }else st = tm + 1;
    }

    cout << st << '\n';
    pr(st, 1);
}

// 8 2 12 
// 1 2 4 2 1 3 5 6 2 3 6 4
# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 8660 KB Output isn't correct
2 Incorrect 16 ms 8676 KB Output isn't correct
3 Incorrect 16 ms 8668 KB Output isn't correct
4 Incorrect 16 ms 8704 KB Output isn't correct
5 Incorrect 15 ms 8660 KB Output isn't correct
6 Incorrect 16 ms 8660 KB Output isn't correct
7 Incorrect 16 ms 8760 KB Output isn't correct
8 Incorrect 16 ms 8660 KB Output isn't correct
9 Correct 26 ms 8908 KB Output is correct
10 Correct 26 ms 8936 KB Output is correct
11 Correct 25 ms 8676 KB Output is correct
12 Correct 41 ms 9424 KB Output is correct
13 Correct 66 ms 10072 KB Output is correct
14 Correct 82 ms 10848 KB Output is correct
15 Incorrect 103 ms 11544 KB Output isn't correct
16 Correct 134 ms 12244 KB Output is correct
17 Correct 142 ms 12892 KB Output is correct
18 Correct 164 ms 13648 KB Output is correct
19 Correct 183 ms 14544 KB Output is correct
20 Correct 153 ms 12948 KB Output is correct