답안 #791934

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791934 2023-07-24T12:40:42 Z matu Job Scheduling (CEOI12_jobs) C++14
15 / 100
182 ms 14504 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 8756 KB Output isn't correct
3 Incorrect 16 ms 8660 KB Output isn't correct
4 Incorrect 17 ms 8688 KB Output isn't correct
5 Incorrect 16 ms 8672 KB Output isn't correct
6 Incorrect 16 ms 8748 KB Output isn't correct
7 Incorrect 16 ms 8660 KB Output isn't correct
8 Incorrect 16 ms 8676 KB Output isn't correct
9 Incorrect 26 ms 8928 KB Output isn't correct
10 Incorrect 26 ms 8932 KB Output isn't correct
11 Incorrect 22 ms 8676 KB Output isn't correct
12 Correct 41 ms 9436 KB Output is correct
13 Incorrect 62 ms 10064 KB Output isn't correct
14 Correct 103 ms 10828 KB Output is correct
15 Incorrect 99 ms 11468 KB Output isn't correct
16 Correct 123 ms 12236 KB Output is correct
17 Incorrect 162 ms 12880 KB Output isn't correct
18 Incorrect 159 ms 13664 KB Output isn't correct
19 Incorrect 182 ms 14504 KB Output isn't correct
20 Incorrect 142 ms 12888 KB Output isn't correct