Submission #1222613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222613		jakeob77	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	271 ms	17772 KiB

jobs

#include <bits/stdc++.h>
#include <bits/extc++.h> 
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define ins insert
//cout<<fixed<<setprecision(3); 3 decimalke brez fixed pa 3 zanesljiva mesta
const int MAXN=2e5+2;
const long long linf=1e18;
const int inf=1e9;
const int mod=1e9+7;


void solve(){
    int n,d,m;cin>>n>>d>>m;
    vector<pair<int,int>>a(m);
    for(int i=0;i<m;i++){
        cin>>a[i].first;
        a[i].second=i+1;
    }
    sort(a.begin(),a.end());
    queue<int>temp;
    for(auto p:a){
        temp.push(p.first+d);
    }
    /*
    auto f=[&](int mid)->bool{
        queue<int>q=temp;
        int e=0;
        for(int i=1;i<=n;i++){
            e=0;
            while(e<mid&&q.size()&&q.front()-d<=i){
                if(q.front()>i) return false;
                q.pop();
            }
        }
        return true;
    };*/   
    int l=1;int r=m;int ans=1;
    while(l<=r){
        int mid=l+(r-l)/2;
        //cout<<mid<<endl;
        bool ok=true;
        queue<int>q=temp;
        int e=0;
        for(int i=1;i<=n;i++){
            e=0;
            while(e<mid&&q.size()&&q.front()-d<=i){
                if(q.front()<i) {
                    //cout<<i<<' '<<q.front()<<' '<<e<<endl;
                    ok=false;
                    break;
                };
                e++;
                q.pop();
            }
        }
        if(ok){
            ans=mid;
            r=mid-1;
        }
        else {
            l=mid+1;
        }
    }
    cout<<ans<<endl;
    l=0;int t=0;
    for(int i=1;i<=n;i++){
        t=0;
        while(t<ans&&l<m&&a[l].first<=i){
            t++;
            cout<<a[l].second<<' ';
            l++;
        }
        cout<<0<<endl;
    }


}   
int main(){
    std::ios::sync_with_stdio(false);
	std::cin.tie(NULL); 
    int t=1;
    while(t--) solve();
    
}

• Subtask 1: 100 / 100