답안 #791945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791945 2023-07-24T12:46:29 Z matu Job Scheduling (CEOI12_jobs) C++14
55 / 100
183 ms 14668 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; 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 8780 KB Output isn't correct
2 Incorrect 16 ms 8812 KB Output isn't correct
3 Incorrect 19 ms 8844 KB Output isn't correct
4 Incorrect 16 ms 8788 KB Output isn't correct
5 Incorrect 15 ms 8792 KB Output isn't correct
6 Incorrect 16 ms 8784 KB Output isn't correct
7 Incorrect 16 ms 8788 KB Output isn't correct
8 Incorrect 16 ms 8812 KB Output isn't correct
9 Correct 26 ms 9072 KB Output is correct
10 Correct 28 ms 9060 KB Output is correct
11 Correct 21 ms 8700 KB Output is correct
12 Correct 40 ms 9480 KB Output is correct
13 Correct 59 ms 10108 KB Output is correct
14 Correct 99 ms 10952 KB Output is correct
15 Incorrect 99 ms 11600 KB Output isn't correct
16 Correct 122 ms 12284 KB Output is correct
17 Correct 143 ms 13028 KB Output is correct
18 Correct 172 ms 13760 KB Output is correct
19 Correct 183 ms 14668 KB Output is correct
20 Correct 145 ms 13120 KB Output is correct