Submission #444407

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
444407	2021-07-14T03:27:10 Z	rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	65 / 100	1000 ms	56264 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;

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	507 ms	11536 KB	Output is correct
2	Correct	487 ms	11532 KB	Output is correct
3	Correct	480 ms	11540 KB	Output is correct
4	Correct	494 ms	11580 KB	Output is correct
5	Correct	490 ms	11572 KB	Output is correct
6	Correct	492 ms	11536 KB	Output is correct
7	Correct	501 ms	11528 KB	Output is correct
8	Correct	515 ms	11576 KB	Output is correct
9	Correct	449 ms	11484 KB	Output is correct
10	Correct	452 ms	11528 KB	Output is correct
11	Correct	250 ms	11452 KB	Output is correct
12	Correct	595 ms	17804 KB	Output is correct
13	Correct	879 ms	26676 KB	Output is correct
14	Execution timed out	1092 ms	29968 KB	Time limit exceeded
15	Execution timed out	1094 ms	34828 KB	Time limit exceeded
16	Execution timed out	1071 ms	41524 KB	Time limit exceeded
17	Execution timed out	1094 ms	50304 KB	Time limit exceeded
18	Execution timed out	1089 ms	52436 KB	Time limit exceeded
19	Execution timed out	1098 ms	56264 KB	Time limit exceeded
20	Execution timed out	1091 ms	50264 KB	Time limit exceeded