Submission #949543

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
949543	2024-03-19T10:29:52 Z	GrindMachine	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	107 ms	3960 KB

jobs

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    int n,d,m; cin >> n >> d >> m;
    vector<int> a(m+5);
    rep1(i,m) cin >> a[i];

    sort(a.begin()+1,a.begin()+m+1);

    auto ok = [&](int mid){
        int ptr = 1;
        rep1(i,n){
            int iter = mid;
            while(ptr <= m and a[ptr] <= i and iter--){
                if(a[ptr]+d < i) return false;
                ptr++;
            }
        }

        return ptr > m;
    };

    int l = 1, r = m;
    int ans = -1;

    while(l <= r){
        int mid = (l+r) >> 1;
        if(ok(mid)){
            ans = mid;
            r = mid-1;
        }
        else{
            l = mid+1;
        }
    }

    cout << ans << endl;
    rep1(i,n){
        cout << 0 << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	860 KB	Output is correct
2	Correct	8 ms	860 KB	Output is correct
3	Correct	8 ms	856 KB	Output is correct
4	Correct	7 ms	864 KB	Output is correct
5	Correct	8 ms	860 KB	Output is correct
6	Correct	7 ms	860 KB	Output is correct
7	Correct	7 ms	860 KB	Output is correct
8	Correct	8 ms	856 KB	Output is correct
9	Correct	15 ms	860 KB	Output is correct
10	Correct	15 ms	1016 KB	Output is correct
11	Correct	11 ms	860 KB	Output is correct
12	Correct	22 ms	1116 KB	Output is correct
13	Correct	33 ms	1624 KB	Output is correct
14	Correct	49 ms	1884 KB	Output is correct
15	Correct	54 ms	2396 KB	Output is correct
16	Correct	74 ms	2808 KB	Output is correct
17	Correct	86 ms	3200 KB	Output is correct
18	Correct	103 ms	3576 KB	Output is correct
19	Correct	107 ms	3960 KB	Output is correct
20	Correct	86 ms	3188 KB	Output is correct