제출 #1358652

#제출 시각아이디문제언어결과실행 시간메모리
1358652yowaineJob Scheduling (CEOI12_jobs)C++20
100 / 100
132 ms21196 KiB
/*
TASK: Job Scheduling (CEOI2012)
LANG: C++
AUTHOR: Yowaine
*/
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int> // {day , idx}
#define day first
#define idx second
#define newline cout << "\n"
#define all(x) x.begin() , x.end()
queue <PII> q;
vector <PII> vec;
int n , d , m;

bool is_possible(int mid){
    int j = 0;
    int sz = vec.size();
    for (int i = 1 ; i <= n ; i++){
        if (j >= sz) return true;
        if (vec[j].day > i) continue;
        if (i > vec[j].day + d) return false;
        j += mid;
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout.tie(0);
    cin >> n >> d >> m;
    for (int i = 1 ; i <= m ; i++){
        int num; cin >> num;
        vec.push_back({num , i});
    }
    sort(all(vec));
    int lo = 1 , hi = 1e6;
    int ans = 0;
    while(lo <= hi){
        int mid = lo + (hi - lo)/2;
        if (is_possible(mid)){
            ans = mid;
            hi = mid - 1;
        }
        else{
            lo = mid + 1;
        }
    }
    for (auto x : vec) q.push(x);
    cout << ans;
    newline;
    for (int i = 1; i <= n ; i++){
        for (int cnt = 1 ; cnt <= ans ; cnt++){
            if (q.front().day > i) break;
            if (q.empty()){
                break;
            }
            cout << q.front().idx << " ";
            q.pop();
        }
        cout << "0";
        newline;
    }
    return 0;
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4

8 0 10
6 6 6 6 6 6 6 6 6 6
*/
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…