Submission #444410

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
444410	2021-07-14T03:39:21 Z	rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	70 / 100	656 ms	56860 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	9272 KB	Output is correct
2	Correct	57 ms	9196 KB	Output is correct
3	Correct	57 ms	9184 KB	Output is correct
4	Correct	57 ms	9264 KB	Output is correct
5	Correct	59 ms	9212 KB	Output is correct
6	Correct	57 ms	9272 KB	Output is correct
7	Correct	58 ms	9272 KB	Output is correct
8	Correct	56 ms	9276 KB	Output is correct
9	Correct	206 ms	9852 KB	Output is correct
10	Correct	206 ms	9748 KB	Output is correct
11	Correct	56 ms	11048 KB	Output is correct
12	Correct	112 ms	16588 KB	Output is correct
13	Correct	165 ms	23332 KB	Output is correct
14	Correct	280 ms	28800 KB	Output is correct
15	Runtime error	261 ms	33440 KB	Memory limit exceeded
16	Runtime error	361 ms	39112 KB	Memory limit exceeded
17	Runtime error	426 ms	45160 KB	Memory limit exceeded
18	Runtime error	472 ms	52252 KB	Memory limit exceeded
19	Runtime error	656 ms	56860 KB	Memory limit exceeded
20	Runtime error	426 ms	45224 KB	Memory limit exceeded