제출 #1317977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317977		woolytank	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	240 ms	14508 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() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m, d;
    cin >> n >> d >> m;
    vector<int> jobs(n);
    deque<pair<int,int>> ids;
    for(int i = 0; i < m; i++) {
        int x;
        cin >> x;
        x--;
        jobs[x]++;
        ids.push_back({x,i + 1});
    }
    sort(ids.begin(), ids.end());
    int L = 0,R = m;
    while(R - L > 1) {
        int mid = (L + R) / 2;
        if(ifPossible(jobs, mid, d)) R = mid;
        else L = mid;
    }
    // for(auto& it : ids) cout << it.first << " " << it.second << endl;
    cout << R << endl;
    vector<int> output;
    for(int i = 0; i < n; i++) {
        int machines = R;
        while(!ids.empty() && machines && ids.front().first <= i) {
            machines--;
            output.push_back(ids.front().second);
            ids.pop_front();
        }
        for(int x : output) cout << x << " ";
        cout << 0 << endl;
        output.clear();
    }
    return 0;
}

• Subtask 1: 100 / 100