Submission #1177832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177832		sergio_sak	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	268 ms	26392 KiB

jobs

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <bit>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <time.h>
#include <random>
#include <iomanip>
#include <inttypes.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace __gnu_pbds;

template <class T>
using Tree = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("O3,Ofast")

#define si(n) scanf("%lld", &n);
#define sl(n) scanf("%lld", &n);
#define sc(n) scanf("%c", &n);
#define sf(n) scanf("%f", &n);
#define slf(n) scanf("%lf", &n);

#define fi first
#define se second
// #define int long long
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define dbg(x) std::cerr << #x << ": " << x << std::endl;

typedef std::set<int> si;
typedef std::pair<int, int> pi;
typedef std::vector<int> vi;
typedef std::vector<std::vector<int>> dvi;
typedef std::unordered_map<int , int> mi;

const float EPS = 1e-9;
const float PI = acos(-1);
const int MAXN = 1000005;
const int MOD = 1000000007;
const int INF = INT32_MAX;

int gcd(int a, int b) {return (b == 0) ? a : gcd(b, a%b);}
int lcm(int a, int b) {return a/gcd(a, b) * b;}

int N, D, M;

std::pair<bool, dvi> isPossibel(const std::vector<pi> &jobs, int exMachina) {
    dvi schedule(N);
    int reqNum = 0;
    
    for(int i = 1; i <= N; ++i) {
        for(int j = 0; j < exMachina; ++j) {

            if(jobs[reqNum].fi > i) break;
            
            if(jobs[reqNum].fi + D >= i)
                schedule[i-1].pb(jobs[reqNum++].se);
            else return {false, schedule};
            
            if(reqNum == M) return {true, schedule};
        }
    }
    
    return {false, schedule};
}

signed main()
{
    
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    std::cin>>N>>D>>M;
    std::vector<pi> jobs(M);

    for(int i = 0; i < M; ++i) {
        int num; std::cin>>num;
        jobs[i] = {num, i+1};
    }

    std::sort(all(jobs));

    dvi result;
    int low = 1, high = M, mid = 0;

    while(low < high) {
        mid = (high+low)/2;

        std::pair<bool, dvi> cur = isPossibel(jobs, mid);

        if(cur.fi) {
            high = mid;
            result = cur.se;
        } else {
            low = mid+1;
        }
    }

    std::cout<<low<<"\n";    
    for(int i = 0; i < N; ++i) {
        for(int &num : result[i]) std::cout<<num<<" ";
        std::cout<<0<<"\n";
    }
    return 0;
}

• Subtask 1: 100 / 100