제출 #1317949

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317949		woolytank	Job Scheduling (CEOI12_jobs)	C++20	85 / 100	291 ms	82528 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

bool ifPossible(vector<int>& jobs, int x, int d) {
    deque<pair<int,int>> dq;
    for(int i = 0; i < jobs.size(); i++) {
        if(!dq.empty() && dq.front().first + d < i) return 0;
        int machines = x;
        while(!dq.empty() && machines) {
            if(dq.front().second > machines) {
                dq.front().second -= machines;
                machines = 0;
            }
            else {
                machines -= dq.front().second;
                dq.pop_front();
            }
        }
        if(jobs[i] > machines) dq.push_back({i, jobs[i] - machines});
    }
    return 1;
}

int main() {
    int n, m, d;
    cin >> n >> d >> m;
    vector<int> jobs(n);
    vector<deque<int>> ids(n);
    for(int i = 0; i < m; i++) {
        int x;
        cin >> x;
        x--;
        jobs[x]++;
        ids[x].push_back(i + 1);
    }
    // When we are at the ith day, jobs with deadline upto i - 1 must be completed
    // for(int i = 0; i < 7; i++) {
    //     cout << jobs[i] << " ";
    // }
    // cout << endl;
    // for(int i = 0; i < n; i++) {
    //     for(int x : ids[i]) cout << x << " ";
    //     cout << endl;
    // }
    int L = 0,R = m;
    while(R - L > 1) {
        int mid = (L + R) / 2;
        if(ifPossible(jobs, mid, d)) R = mid;
        else L = mid;
    }
    cout << R << endl;
    deque<pair<int,int>> dq;
    vector<vector<int>> output(n);

    for(int i = 0; i < jobs.size(); i++) {
        int machines = R;
        while(!dq.empty() && machines) {
            if(dq.front().second > machines) {
                dq.front().second -= machines;
                auto& ls = ids[dq.front().first];
                while(machines) {
                    output[i].push_back(ls.front());
                    ls.pop_front();
                    machines--;
                }
            }
            else {
                auto& ls = ids[dq.front().first];
                while(dq.front().second) {
                    output[i].push_back(ls.front());
                    ls.pop_front();
                    machines--;
                    dq.front().second--;
                }
                dq.pop_front();
            }
        }
        if(jobs[i] > machines) {
            dq.push_back({i, jobs[i] - machines});
            auto& ls = ids[i];
            while(machines) {
                output[i].push_back(ls.front());
                ls.pop_front();
                machines--;
            }
        }
        else {
            auto& ls = ids[i];
            while(!ls.empty()) {
                output[i].push_back(ls.front());
                ls.pop_front();
                machines--;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        for(int x : output[i]) cout << x << " ";
        cout << 0 << endl;
    }
    return 0;
}

• Subtask 1: 85 / 100