Submission #586090

#	Time	Username	Problem	Language	Result	Execution time	Memory
586090		rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	161 ms	45264 KiB

jobs

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
const int MN=1e5+10;
const int MOD=1e9+7;
using pi = pair<ll, ll>;
using ti = tuple<ll, ll, ll>;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define MAX_SIZE 1000005
#define lcm(a, b) (a*b)/__gcd(a, b)

struct Edge{
    ll val, index;
};

bool comp(const Edge& x, const Edge& y){
    return x.val < y.val;
}


ll n, d, m; 
vector<Edge> nums;
vector<ll> adj[MN];
vector<ll> temp[MN];

bool f(ll x){
    // binary search check (greedy)
    for (int i=0; i<MN; i++){
        temp[i].clear();
    }
    ll dp[MN]={0};
    for (int i=0; i<nums.size(); i++){
        ll curr=nums[i].val;
        if (i-x>=0){
            curr=max(curr, dp[i-x]+1);
        }
        if (curr-nums[i].val>d){
            return false;
        }
        dp[i]=curr;
        temp[curr].pb(nums[i].index);
    }
    return true;
}

ll binaryMin(ll low, ll high){
    // for min
    ll res=0;
    while (low<=high){
        ll mid=(low+high)/2;
        if (f(mid)){
            for (int i=0; i<MN; i++){
                adj[i].clear();
            }
            for (int i=0; i<MN; i++){
                for (auto num: temp[i]){
                    adj[i].pb(num);
                }
            }
            res=mid;
            high=mid-1;
        }
        else{
            low=mid+1;
        }
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>d>>m;

    for (int i=0; i<m; i++){
        ll num; cin>>num;
        nums.pb({num, i+1});
    }

    sort(nums.begin(), nums.end(), comp);

    ll ans=binaryMin(1, m);

    cout<<ans<<endl;

    for (int i=1; i<=n; i++){
        for (auto num: adj[i]){
            cout<<num<<" ";
        }
        cout<<0<<endl;
    }



    


}

Compilation message (stderr)

jobs.cpp: In function 'bool f(ll)':
jobs.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i=0; i<nums.size(); i++){
      |                   ~^~~~~~~~~~~~

• Subtask 1: 55 / 100