Submission #444408

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
444408	2021-07-14T03:37:28 Z	rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	70 / 100	648 ms	56848 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	56 ms	9272 KB	Output is correct
2	Correct	57 ms	9184 KB	Output is correct
3	Correct	57 ms	9276 KB	Output is correct
4	Correct	57 ms	9200 KB	Output is correct
5	Correct	56 ms	9200 KB	Output is correct
6	Correct	60 ms	9192 KB	Output is correct
7	Correct	56 ms	9196 KB	Output is correct
8	Correct	57 ms	9204 KB	Output is correct
9	Correct	208 ms	10000 KB	Output is correct
10	Correct	202 ms	9724 KB	Output is correct
11	Correct	55 ms	10940 KB	Output is correct
12	Correct	113 ms	16536 KB	Output is correct
13	Correct	164 ms	23448 KB	Output is correct
14	Correct	251 ms	28708 KB	Output is correct
15	Runtime error	258 ms	33492 KB	Memory limit exceeded
16	Runtime error	361 ms	39164 KB	Memory limit exceeded
17	Runtime error	421 ms	45236 KB	Memory limit exceeded
18	Runtime error	473 ms	52236 KB	Memory limit exceeded
19	Runtime error	648 ms	56848 KB	Memory limit exceeded
20	Runtime error	424 ms	45152 KB	Memory limit exceeded