Submission #896256

#	Time	Username	Problem	Language	Result	Execution time	Memory
896256		akkshaysr	Job Scheduling (CEOI12_jobs)	C++17	60 / 100	173 ms	14164 KiB

jobs

#include <bits/stdc++.h>
#define fr first
#define se second
#define rep(i,a,b) for(int i = a; i < (b); ++i)
#define repr(i,a,b) for(int i = a; i > (b); --i)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define IN(i,l,r) (l<i&&i<r)
#define pb push_back
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef long long ll;
const int U = 1e6+2;
int N,D,M;
pi job[U];
int jd[U/10 + 1];

bool check(int m){
    int day = 0,t = 0;
    while(day < N && t < M){
        ++day;
        if(job[t].fr + D < day){
            return false;
        }
        t = min(t+m,jd[day]);
        if(job[t-1].fr + D < day){
            return false;
        }
    }
    return true;
}

int main(){
    cin.tie(0)->sync_with_stdio(false);
    cin >> N >> D >> M;
    rep(i,0,M){
        cin >> job[i].fr;
        jd[job[i].fr] += 1;
        job[i].se = i+1;
    }
    rep(i,2,N+1) jd[i] += jd[i-1];
    sort(job,job+M);
    int lo=1,hi=U;
    while(lo < hi){
        ll m = (lo+hi)/2;
        if(check(m)){
            hi = m;
        }else{
            lo = m+1;
        }
    }
    cout << hi << '\n';
    int day = 0,t = 0;
    while(day < N){
        ++day;
        int t_ = min(t+hi,jd[day]);
        rep(i,t,t_){
            cout << job[i].se << ' ';
        }
        cout << "0\n";
        t = t_;
    }
}

• Subtask 1: 60 / 100