Submission #444407

#	Time	Username	Problem	Language	Result	Execution time	Memory
444407		rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	65 / 100	1098 ms	56264 KiB

jobs

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

typedef long long ll;
const int MN=1e5+10;
const int MOD=1e9+7;
using pi = pair<ll, ll>;
#define pb push_back
#define mp make_pair
#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> store[MN];

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

    for (int i=0; i<n; i++){
        store[i].clear();
    }

    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 first=curr.begin();
        if (nums[i].val>*first){
            store[nums[i].val-1].pb(nums[i].index);
            curr.erase(first);
            curr.insert(nums[i].val);
        }
        else{
            ll diff=*first-nums[i].val+1;
            if (diff>d){
                works=false;
                break;
            }
            else{
                store[*first].pb(nums[i].index);
                curr.erase(first);
                curr.insert(*first + 1);
            }
        }
    }

    if (works){
        for (int i=0; i<n; i++){
            adj[i].clear();
        }
        for (int i=0; i<n; i++){
            for (int j=0; j<store[i].size(); j++){
                adj[i].pb(store[i][j]);
            }
        }
        return true;
    }
    else{
        return false;
    }

}

ll binaryMin(ll low, ll high){
    // for min
    ll res=0;
    while (low<=high){
        ll mid=(low+high)/2;
        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);
    
    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=0; i<n; i++){
        for (int j=0; j<adj[i].size(); j++){
            cout<<adj[i][j]<<" ";
        }
        cout<<0<<endl;
    }






}

Compilation message (stderr)

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

• Subtask 1: 65 / 100