Submission #722333

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
722333	2023-04-11T18:40:31 Z	ducanh1234	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	242 ms	20800 KB

jobs

#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

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	2388 KB	Output is correct
2	Correct	16 ms	2516 KB	Output is correct
3	Correct	17 ms	2412 KB	Output is correct
4	Correct	19 ms	2408 KB	Output is correct
5	Correct	17 ms	2508 KB	Output is correct
6	Correct	17 ms	2516 KB	Output is correct
7	Correct	17 ms	2388 KB	Output is correct
8	Correct	17 ms	2488 KB	Output is correct
9	Correct	32 ms	2568 KB	Output is correct
10	Correct	31 ms	2636 KB	Output is correct
11	Correct	32 ms	2416 KB	Output is correct
12	Correct	48 ms	4728 KB	Output is correct
13	Correct	71 ms	6900 KB	Output is correct
14	Correct	152 ms	9260 KB	Output is correct
15	Correct	119 ms	11476 KB	Output is correct
16	Correct	173 ms	13796 KB	Output is correct
17	Correct	184 ms	16024 KB	Output is correct
18	Correct	235 ms	18344 KB	Output is correct
19	Correct	242 ms	20800 KB	Output is correct
20	Correct	179 ms	15996 KB	Output is correct