Submission #949547

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
949547	2024-03-19T10:32:20 Z	GrindMachine	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	239 ms	13892 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<pii> a(m+5);
    rep1(i,m) cin >> a[i].ff;
    rep1(i,m) a[i].ss = i;

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

    auto ok = [&](int mid, int t){
        int ptr = 1;
        rep1(i,n){
            int iter = mid;
            vector<int> guys;

            while(ptr <= m and a[ptr].ff <= i and iter--){
                if(a[ptr].ff+d < i) return false;
                guys.pb(a[ptr].ss);
                ptr++;
            }

            if(t){
                trav(x,guys) cout << x << " ";
                cout << 0 << endl;
            }
        }

        return ptr > m;
    };

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

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

    cout << ans << endl;
    ok(ans,1);
}

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	24 ms	2132 KB	Output is correct
2	Correct	23 ms	2236 KB	Output is correct
3	Correct	19 ms	2120 KB	Output is correct
4	Correct	18 ms	2140 KB	Output is correct
5	Correct	18 ms	2140 KB	Output is correct
6	Correct	20 ms	2392 KB	Output is correct
7	Correct	19 ms	2392 KB	Output is correct
8	Correct	19 ms	2140 KB	Output is correct
9	Correct	29 ms	2036 KB	Output is correct
10	Correct	29 ms	2036 KB	Output is correct
11	Correct	24 ms	1624 KB	Output is correct
12	Correct	57 ms	3156 KB	Output is correct
13	Correct	73 ms	4596 KB	Output is correct
14	Correct	117 ms	6228 KB	Output is correct
15	Correct	118 ms	7696 KB	Output is correct
16	Correct	162 ms	9040 KB	Output is correct
17	Correct	189 ms	10636 KB	Output is correct
18	Correct	224 ms	12180 KB	Output is correct
19	Correct	239 ms	13892 KB	Output is correct
20	Correct	197 ms	10536 KB	Output is correct