제출 #1363667

#제출 시각아이디문제언어결과실행 시간메모리
1363667nezuko2410Job Scheduling (CEOI12_jobs)C++20
55 / 100
95 ms17288 KiB
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N=1e5+10;
int n,d,m,i,a[N],l,r,mid,res;
vector<pair<int,int>>v;
bool check(int x) {
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>hc;
    int j=0;
    for (int i=1; i<=n; i++) {
        while (j<v.size() && v[j].fi==i) {
            hc.push({v[j].fi+d,v[j].se});
            j++;
        }
        for (int k=1; k<=x; k++) {
            if (hc.empty()) break;
            if (hc.top().fi<i) return false;
            hc.pop();
        }
    }
    return hc.empty();
}
signed main () {
    cin>>n>>d>>m;
    for (i=1; i<=m; i++) {
        cin>>a[i];
        v.push_back({a[i],i});
    }
    sort(v.begin(),v.end());
    l=1,r=m;
    while(l<=r) {
        mid=(l+r)/2;
        if (check(mid)) {
            res=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout<<res<<"\n";
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    int j=0;
    for (i=1; i<=n; i++) {
        while (j<v.size() && v[j].fi==i) {
            pq.push({v[j].fi+d,v[j].se});
            j++;
        }
        int cnt=0;
        while (!pq.empty() && cnt<res) {
            auto t=pq.top();
            pq.pop();
            cout<<t.se<<" ";
            cnt++;
        }
        cout<<0<<"\n";
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…