제출 #1270391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270391		xqysp	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	379 ms	27016 KiB

jobs

// https://oj.uz/problem/view/CEOI12_jobs

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, D, M;
    cin >> N >> D >> M;
    vector<pair<int,int>> requests;
    requests.resize(M);
    for (int i = 0; i < M; i++) {
        int a;
        cin >> a;
        requests[i]=make_pair(a,i+1);
    }
    sort(requests.begin(), requests.end());
    int left = 1, right = M;
    vector<vector<int>> bestOutput;
    
    while (left <= right) {
        vector<vector<int>> outputVec;
        int mid = (left + right) / 2;
        // cout<<mid<<endl;
        // 8 2 12 1 2 4 2 1 3 5 6 2 3 6 4
        // 1 2 4 2 1 3 5 6 2 3 6 4
        // 1,1,2,2,2,3,3,4,4,5,6,6
        int index = 0;
        bool enough = true;
        outputVec.clear();
        outputVec.resize(N);
        for (int day = 1; day <= N; day++) {
            
            int count = 0;
            while (count < mid && index < M) {
                
                if (requests[index].first + D < day) {
                    enough = false;
                    break;
                }
               
                if (requests[index].first > day) {
                    break;
                }
                outputVec[day - 1].push_back(requests[index].second);
                index++;
                count++;
            }
            if (enough == false) {
                break;
            }
        }
        if(index<M){
            enough=false;
        }
        if (enough == true) {
            bestOutput=outputVec;
            right = mid-1;
        } else {
            left = mid + 1;
        }
    }
    cout << left<<endl;
    //output

    for(int i = 0; i< N;i++){
        for(auto num: bestOutput[i]){
            cout<<num<<" ";
        }
        cout<<0<<endl;
    }
    return 0;
}

• Subtask 1: 100 / 100