Submission #1318673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318673		khanhphucscratch	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	373 ms	11316 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
vector<int> order[100005];
bool check(int x, int n, int d)
{
    list<int> st;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < order[i].size(); j++) st.push_back(i);
        int len = st.size();
        for(int j = 1; j <= min(x, len); j++){
            if(st.front() < i-d) return 0;
            st.pop_front();
        }
    }
    return st.size() == 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, d, m; cin>>n>>d>>m;
    for(int i = 1; i <= m; i++){
        int x; cin>>x;
        order[x].push_back(i);
    }
    int l = 1, r = m, ans = 0;
    while(l <= r){
        int mid = (l+r)/2;
        if(check(mid, n, d) == 1){ans = mid; r = mid-1;}
        else l = mid+1;
    }
    cout<<ans<<'\n';
    list<int> st;
    for(int i = 1; i <= n; i++){
        for(int j : order[i]) st.push_back(j);
        int len = st.size();
        for(int j = 1; j <= min(len, ans); j++){
            cout<<st.front()<<" ";
            st.pop_front();
        }
        cout<<0<<'\n';
    }
}

• Subtask 1: 100 / 100