Submission #112870

#	Time	Username	Problem	Language	Result	Execution time	Memory
112870		Hassoony	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	672 ms	25228 KiB

jobs

#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 (stderr)

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 / 100