제출 #677956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677956		Raed	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	381 ms	28904 KiB

jobs

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define ss second
    #define ff first
    #define pb push_back
    #define mk make_pair
    #define mt make_tuple
    #define all(x) (x).begin(), (x).end()
    ll n,m,a[2001000],k;
    bool go(ll mid){
        int o=0,d=0;
        for(int i=1;i<=n;i++){
            o=0;
            for(int j=d;j<m;j++){
                if(i-a[j]>k){
                    return false;
                }
                if(a[j]>i)
                break;
                o++;
                d++;
                if(o>=mid){
                    break;
                }
            }
        }
        if(d<m)
        return false;
        return true;
    }
    int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cin>>n>>k>>m;
        vector<pair<ll,ll> >v;
        for(int i=0;i<m;i++){
            cin>>a[i];
            v.pb({a[i],i+1});
        }
        sort(a,a+m);
        ll l=0,r=1e9,ans=1e9;
        while(l<=r){
            ll mid=(l+r)/2;
            if(go(mid)){
                r=mid-1;
                ans=mid;
            }
            else{
                l=mid+1;
            }
        }
        cout<<ans<<endl;
        sort(v.begin(),v.end());
        int o=0,d=0;
        for(int i=1;i<=n;i++){
            o=0;
            for(int j=d;j<m;j++){
                if(a[j]>i)
                break;
                o++;
                d++;
                cout<<v[j].ss<<" ";
                if(o>=ans){
                    break;
                }
            }
            cout<<0<<endl;
        }
    }

• Subtask 1: 100 / 100