Submission #1157543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157543		ocasu	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	266 ms	17804 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    int n,d,m; cin>>n>>d>>m;
    vector<vector<int>> x(n+1);
    for (int i=1; i<=m; i++) {
        int z; cin>>z;
        x[z].push_back(i);
    }
    
    int l = 1, r = 1e6+5; 
    while (l != r) { 
        int mid = (l+r)/2; 
        //mid=1;
        bool ok=true;
        queue<pair<int,int>> s;
        for (int i=1; i<=n; i++){
            for (auto j: x[i]){
                s.push({i,j});
            }
            if (!s.empty() and (i-(s.front()).first > d)){
                ok=false;
                break;
            }
            for (int i=1; i<=mid and !s.empty(); i++){
                s.pop();
            }
        }
        //cout<<(int)(s.size())<<'\n';  
        if (!s.empty()) ok=false;

        //cout<<ok<<'\n';
        //break;

        if (ok) { 
            r = mid; 
        } 
        else { 
            l = mid+1; 
        } 
    }
    int ans=l;
    cout<<ans<<'\n';
    set<pair<int,int>> s;
    for (int i=1; i<=n; i++){
        for (auto j: x[i]){
            s.insert({i,j});
        }
        for (int i=1; i<=ans and !s.empty(); i++){
            cout<<(*s.begin()).second<<' ';
            s.erase(s.begin()); 
        }
        cout<<0<<'\n';
    }

}

• Subtask 1: 100 / 100