제출 #267142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
267142		Sorting	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	281 ms	13688 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

const int k_N = 1e5 + 3;
const int k_M = 1e6 + 3;

int n, d, m;
vector<int> jobs[k_N];

bool check(int mid){
    queue<int> q;
    for(int i = 1; i <= n; ++i){
        for(int x: jobs[i])
            q.push(i);

        int t = mid;
        while(t-- && !q.empty()){
            if(q.front() + d < i)
                return false;
            q.pop();
        }
    }
    return true;
}

void output(int mid){
    queue<int> q;
    for(int i = 1; i <= n; ++i){
        for(int x: jobs[i])
            q.push(x);

        int t = mid;
        while(t-- && !q.empty()){
            cout << q.front() << " ";
            q.pop();
        }
        cout << "0\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> d >> m;
    for(int i = 1; i <= m; ++i){
        int x;
        cin >> x;
        jobs[x].push_back(i);
    }

    int l = 0, r = k_M;
    while(l != r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << "\n";
    output(l);    
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

컴파일 시 표준 에러 (stderr) 메시지

jobs.cpp: In function 'bool check(int)':
jobs.cpp:14:17: warning: unused variable 'x' [-Wunused-variable]
   14 |         for(int x: jobs[i])
      |                 ^

• Subtask 1: 100 / 100