oj.uz

Submission #112870

# Submission time Handle Problem Language Result Execution time Memory
112870 2019-05-22T10:55:23 Z Hassoony Job Scheduling (CEOI12_jobs) C++17
100 / 100
 672 ms 25228 KB 
#include <bits/stdc++.h>

using namespace std;
const int MX=2e5+9;
int n,m,d,a[MX],b[MX];
bool check(int mach){
    for(int i=1;i<=n;i++)a[i]=b[i];
    multiset<int>ms;
    int last=0;
    for(int i=1;i<=2*n;i++){
        mach+=last;
        last=0;
        while(mach&&!ms.empty()){
            if(*ms.begin()<i)return 0;
            ms.erase(ms.begin());
            mach--;
            last++;
        }
        while(mach&&a[i]){
            mach--;
            a[i]--;
            last++;
        }
        while(a[i]){
            ms.insert(i+d);
            a[i]--;
        }
    }
    return 1;
}
int bn(int l,int r){
    int ans=m;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    return ans;
}
vector<int>v[MX],v1[MX];
void fix(int mach){
    for(int i=1;i<=n;i++)a[i]=b[i];
    multiset<pair<int,int> >ms;
    int last=0;
    for(int i=1;i<=2*n;i++){
        mach+=last;
        last=0;
        while(mach&&!ms.empty()){
            v[i].push_back(ms.begin()->second);
            ms.erase(ms.begin());
            mach--;
            last++;
        }
        while(mach&&v1[i].size()){
            mach--;
            v[i].push_back(v1[i].back());
            v1[i].pop_back();
            last++;
        }
        while(v1[i].size()){
            ms.insert({i+d,v1[i].back()});
            v1[i].pop_back();
        }
    }
    for(int i=1;i<=n;i++){
        for(auto pp:v[i]){
            cout<<pp<<" ";
        }
        puts("0");
    }
}
int main(){
    cin>>n>>d>>m;
    for(int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        a[x]++;
        v1[x].push_back(i);
    }
    for(int i=1;i<=n;i++)b[i]=a[i];
//    check(1);
    int ans=bn(1,m);
    cout<<ans<<endl;
    fix(ans);
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 13680 KB Output is correct
2 Correct 167 ms 13680 KB Output is correct
3 Correct 164 ms 13676 KB Output is correct
4 Correct 174 ms 13740 KB Output is correct
5 Correct 157 ms 13792 KB Output is correct
6 Correct 186 ms 13680 KB Output is correct
7 Correct 167 ms 13780 KB Output is correct
8 Correct 157 ms 13684 KB Output is correct
9 Correct 75 ms 12664 KB Output is correct
10 Correct 116 ms 12860 KB Output is correct
11 Correct 52 ms 11384 KB Output is correct
12 Correct 206 ms 13868 KB Output is correct
13 Correct 205 ms 15864 KB Output is correct
14 Correct 350 ms 19248 KB Output is correct
15 Correct 146 ms 17912 KB Output is correct
16 Correct 215 ms 20260 KB Output is correct
17 Correct 398 ms 24724 KB Output is correct
18 Correct 672 ms 23800 KB Output is correct
19 Correct 608 ms 25228 KB Output is correct
20 Correct 390 ms 24824 KB Output is correct