제출 #1270388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270388		xqysp	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	444 ms	42840 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 i = 1; i <= N; i++) {
            if (index >= M) {
                break;
            }
            for (int j = 0; j < mid; j++) {
                if (index >= M) {
                    break;
                }
                if (requests[index].first > i + D) {
                    enough = false;
                    break;
                }
                if (requests[index].first > i) {
                    break;
                }
                outputVec[i-1].push_back(requests[index].second);
                // cout<<"*"<<i-1<<endl;
                index++;
            }
            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: 40 / 100