oj.uz

Submission #698908

# Submission time Handle Problem Language Result Execution time Memory
698908 2023-02-14T17:16:27 Z Smeagol Job Scheduling (CEOI12_jobs) C++17
100 / 100
 380 ms 17180 KB 
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,d,m;
    cin>>n>>d>>m;
    vector<pair<int,int>> req(m);
    for(int i=0;i<m;i++){
        cin>>req[i].first;
        req[i].second=i+1;
    }
    sort(req.begin(),req.end());

    int lo=0,hi=1e9,ans=1e9;
    while(lo<=hi){
        int mid=lo+(hi-lo)/2;

        bool can=true;
        int p=0;
        for(int i=1;i<=n;i++){
            if(!can)break;
            for(int t=0;t<mid&&p<m;t++){
                if(req[p].first>i) break;
                if(i-req[p].first>d){
                    can=false;
                    break;
                }
                p++;
            }
        }
        if(p<m) can=false;

        if(can){
            hi=mid-1;
            ans=min(ans,mid);
        }
        else lo=mid+1;
    }
    cout<<ans<<"\n";

    int p=0;
    for(int i=1;i<=n;i++){
        for(int t=0;t<ans&&p<m;t++){
            if(req[p].first>i)break;
            cout<<req[p].second<<" ";
            p++;
        }
        cout<<"0\n";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1868 KB Output is correct
2 Correct 29 ms 1864 KB Output is correct
3 Correct 31 ms 1864 KB Output is correct
4 Correct 29 ms 1900 KB Output is correct
5 Correct 34 ms 1896 KB Output is correct
6 Correct 42 ms 1868 KB Output is correct
7 Correct 29 ms 1900 KB Output is correct
8 Correct 29 ms 1896 KB Output is correct
9 Correct 43 ms 2072 KB Output is correct
10 Correct 43 ms 1996 KB Output is correct
11 Correct 39 ms 1992 KB Output is correct
12 Correct 77 ms 3916 KB Output is correct
13 Correct 134 ms 5692 KB Output is correct
14 Correct 184 ms 8012 KB Output is correct
15 Correct 190 ms 9436 KB Output is correct
16 Correct 273 ms 11960 KB Output is correct
17 Correct 344 ms 13948 KB Output is correct
18 Correct 317 ms 15096 KB Output is correct
19 Correct 380 ms 17180 KB Output is correct
20 Correct 295 ms 13952 KB Output is correct