Submission #722333

#TimeUsernameProblemLanguageResultExecution timeMemory
722333ducanh1234Job Scheduling (CEOI12_jobs)C++14
100 / 100
242 ms20800 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long 

#define rep(i, b) for(int i = 0; i < (int)b; i++)
#define FOR(i, a, b) for(int i = a; i < (int)b; i++)
#define dbg(v) cerr << "Line(" << __LINE__ << ") -> " << #v << " = " << (v) << endl;
#define debug(a, b) cerr << "[" << #a << ", " << #b << "] = [" << a << ", " << b << "]\n";

template<class T> inline void read(T& t){ cin >> t; }
template<class T, class... H> inline void read(T& t, H&... h){ cin >> t; read(h...); }
template<class T> inline void read(vector<T>& t){ for(auto&x : t) read(x); } 
template<class T, class... H> inline void read(vector<T>& t, vector<H>&... h){ read(t); read(h...); }

template<class T> inline void wt(const T t) { cout << t; } 
template<class T> inline void print(const T t){ cout << t << "\n";}
template<class T, class... H> inline void wt(const T& t, const H&... h){ cout << t; wt(h...); }
template<class T, class... H> inline void print(const T& t, const H&... h){ cout << t; cout << " "; print(h...);}
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(a) (int)a.size()
#define f first
#define s second

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int n, d, m; read(n, d, m);
    vector<pair<int, int>> v(m);
    rep(i, m) read(v[i].f), v[i].s = i + 1;
    sort(all(v)); 
    
    // bs in vector v -> if(check(mid)) r = mid - 1 else l = mid + 1;
    auto check = [&](int mid){
        int tmp = 0, cnt = 0, ans = 0;
        rep(i, m){
            cnt = 0;
            if(i + 1 - v[tmp].f > d || i + 1 > n) return false;
            while(v[tmp].f <= i + 1 && cnt < mid && tmp < m){
                tmp++, cnt++;
                // assert(mid == 6);
                // dbg(i);
            }
            if(tmp == m) break;
            ans++;
        }
        return tmp == m && ans <= n;
    };
    int l = 1, r = m, res = 0;
    while(l <= r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid - 1, res = mid;
        else l = mid + 1;
    }
    print(res); 
    int tmp = 0, cnt = 0;
    rep(i, n){
        cnt = 0;
        if(tmp <= m){
            while(v[tmp].f <= i + 1 && cnt < res && tmp < m){
                wt(v[tmp++].s, ' '); cnt++;
            } 
        }
        print(0);
    }
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |         int mid = l + r >> 1;
      |                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...