oj.uz

Submission #112869

# Submission time Handle Problem Language Result Execution time Memory
112869 2019-05-22T10:54:49 Z Hassoony Job Scheduling (CEOI12_jobs) C++17
0 / 100
 59 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;
const int MX=2e6+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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 55 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 56 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 56 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 55 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 54 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 56 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 53 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 50 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 55 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 55 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 57 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 52 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 55 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 59 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 59 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 56 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 59 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 55 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 53 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)