Submission #1351592

#TimeUsernameProblemLanguageResultExecution timeMemory
1351592chosencheeseJob Scheduling (CEOI12_jobs)C++20
25 / 100
96 ms13880 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pr pair
#define sz size
#define X first
#define tp tuple
#define Y second
#define db double
#define sg string
#define vt vector
#define gt greater
#define ll long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define pq priority_queue
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fup(i, s, e) for (int i = (s); i < (int)(e); i++)
#define fdn(i, s, e) for (int i = (s); i > (int)(e); i--)
#define fio(name) freopen(#name ".in", "r", stdin); freopen(#name ".out", "w", stdout);
#define indexed_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

const int MXINT = 1e9;
const ll MXLL = 4e18;
const int MOD = 1e9 + 7;

struct task{
    int sub_date, id;

    bool operator<(const task& others) const{
        return sub_date < others.sub_date;
    }
};

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0);
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    
    /*#else
        fio();*/
    
    #endif

    int n, d, m; cin >> n >> d >> m;
    vt<task> tasks(m + 1);
    fup(i, 1, m + 1){
        int date; cin >> date;
        tasks[i] = {date, i};
    }
    sort(tasks.begin() + 1, tasks.end());

    auto check = [&tasks, &n, &d, &m](int num)->bool{
        int time = 0, it = 0;
        while(it <= m){
            time++;
            fup(r, 0, num){
                it++;
                if(!it > n){
                    int ddl = tasks[it].sub_date + d;
                    if(ddl < time) return false;
                }
            }
        }
        return (time <= n);
    };

    auto bfind = [&m, &check]()->int{
        int lo = 1, hi = m;
        while(lo < hi){
            int mid = lo + (hi - lo) / 2;
            if(check(mid)){
                hi = mid;
            }else{
                lo = mid + 1;
            }
        }
        return lo;
    };

    int ans = bfind();
    cout << ans << "\n";
    int it = 1;
    fup(i, 0, n){
        for(int r = 0; it <= m && r < ans; r++) cout << tasks[it++].id << " ";
            cout << 0 << "\n";
    }
    //cout << check(1);
}
#Verdict Execution timeMemoryGrader output
Fetching results...