Submission #436052

#	Time	Username	Problem	Language	Result	Execution time	Memory
436052		rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	27 / 100	1108 ms	65540 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MN=1e5+10;
const int MOD=1e9+7;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define MAX LLONG_MAX
#define MIN LLONG_MIN



struct Edge{
    ll val, index;
};

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


ll d, n;
vector<Edge> nums;
vector<ll> req[MN];

bool f(ll x){
    // binary search check (greedy)
    
    if (x>n){
        return true;
    }

    multiset<ll> curr;
    for (int i=0; i<x; i++){
        curr.insert(0);
    }
    bool works=true;

    for (int i=0; i<nums.size(); i++){
        auto it=curr.begin();
        ll start=*it;
        start=max(nums[i].val, start);
        if (start-nums[i].val>d){
            works=false;
            break;
        }
        req[start].pb(nums[i].index+1);
        curr.insert(start+1);
        curr.erase(it);

    }

    if (works){
        return true;
    }
    for (int i=0; i<MN; i++){
        req[i].clear();
    }
    return false;
}

ll binaryMin(ll low, ll high){
    // for min
    ll res=0;
    while (low<=high){
        ll mid=(low+high)/2;
        // cout<<mid<<endl;
        if (f(mid)){
            res=mid;
            high=mid-1;
        }
        else{
            low=mid+1;
        }
    }
    return res;
}




int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    ll m; cin>>n>>d>>m;
    
    for (int i=0; i<m; i++){
        ll num; cin>>num;
        nums.pb({num, i});
    }

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

    ll ans=binaryMin(0, INT_MAX);

    cout<<ans<<endl;
    for (int i=1; i<=n; i++){
        for (int j=0; j<req[i].size(); j++){
            cout<<req[i][j]<<" ";
        }
        cout<<0<<endl;
    }
    





}

Compilation message (stderr)

jobs.cpp: In function 'bool first(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++){
      |                   ~^~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:102:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int j=0; j<req[i].size(); j++){
      |                       ~^~~~~~~~~~~~~~

• Subtask 1: 27 / 100