Submission #444410

#	Time	Username	Problem	Language	Result	Execution time	Memory
444410		rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	70 / 100	656 ms	56860 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;

    ll day=1;
    ll left=x;

    for (int i=0; i<nums.size(); i++){
        if (day-nums[i].val>d){
            works=false;
            break;
        }
        day=max(day, nums[i].val);
        store[day-1].pb(nums[i].index);

        left--;

        if (left==0){
            left=x;
            day++;
        }
    }

    // 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:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i=0; i<nums.size(); i++){
      |                   ~^~~~~~~~~~~~
jobs.cpp:91:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             for (int j=0; j<store[i].size(); j++){
      |                           ~^~~~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:138:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         for (int j=0; j<adj[i].size(); j++){
      |                       ~^~~~~~~~~~~~~~

• Subtask 1: 70 / 100