Submission #677956

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
677956	2023-01-04T18:00:29 Z	Raed	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	381 ms	28904 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	3640 KB	Output is correct
2	Correct	31 ms	3648 KB	Output is correct
3	Correct	32 ms	3628 KB	Output is correct
4	Correct	31 ms	3644 KB	Output is correct
5	Correct	31 ms	3636 KB	Output is correct
6	Correct	36 ms	3668 KB	Output is correct
7	Correct	31 ms	3708 KB	Output is correct
8	Correct	32 ms	3632 KB	Output is correct
9	Correct	148 ms	3816 KB	Output is correct
10	Correct	143 ms	3792 KB	Output is correct
11	Correct	30 ms	3716 KB	Output is correct
12	Correct	62 ms	7160 KB	Output is correct
13	Correct	94 ms	11548 KB	Output is correct
14	Correct	146 ms	13300 KB	Output is correct
15	Correct	155 ms	16500 KB	Output is correct
16	Correct	211 ms	21832 KB	Output is correct
17	Correct	235 ms	22484 KB	Output is correct
18	Correct	263 ms	25536 KB	Output is correct
19	Correct	381 ms	28904 KB	Output is correct
20	Correct	239 ms	22464 KB	Output is correct