Submission #436052

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
436052	2021-06-24T07:00:57 Z	rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	27 / 100	1000 ms	65540 KB

jobs

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

typedef long long ll;
const int MN=1e5+10;
const int MOD=1e9+7;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define MAX LLONG_MAX
#define MIN LLONG_MIN



struct Edge{
    ll val, index;
};

bool comp(const Edge& x, const Edge& y){
    return x.val < y.val;
}


ll d, n;
vector<Edge> nums;
vector<ll> req[MN];

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

    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 it=curr.begin();
        ll start=*it;
        start=max(nums[i].val, start);
        if (start-nums[i].val>d){
            works=false;
            break;
        }
        req[start].pb(nums[i].index+1);
        curr.insert(start+1);
        curr.erase(it);

    }

    if (works){
        return true;
    }
    for (int i=0; i<MN; i++){
        req[i].clear();
    }
    return false;
}

ll binaryMin(ll low, ll high){
    // for min
    ll res=0;
    while (low<=high){
        ll mid=(low+high)/2;
        // cout<<mid<<endl;
        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);
    
    ll m; cin>>n>>d>>m;
    
    for (int i=0; i<m; i++){
        ll num; cin>>num;
        nums.pb({num, i});
    }

    sort(nums.begin(), nums.end(), comp);

    ll ans=binaryMin(0, INT_MAX);

    cout<<ans<<endl;
    for (int i=1; i<=n; i++){
        for (int j=0; j<req[i].size(); j++){
            cout<<req[i][j]<<" ";
        }
        cout<<0<<endl;
    }
    





}

Compilation message

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

Subtask #1

27.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	62 ms	5432 KB	Output isn't correct
2	Incorrect	70 ms	5264 KB	Output isn't correct
3	Incorrect	60 ms	5276 KB	Output isn't correct
4	Incorrect	60 ms	5188 KB	Output isn't correct
5	Incorrect	60 ms	5260 KB	Output isn't correct
6	Incorrect	60 ms	5392 KB	Output isn't correct
7	Incorrect	61 ms	5180 KB	Output isn't correct
8	Incorrect	60 ms	5184 KB	Output isn't correct
9	Correct	464 ms	10620 KB	Output is correct
10	Correct	464 ms	11100 KB	Output is correct
11	Correct	108 ms	8504 KB	Output is correct
12	Partially correct	314 ms	18480 KB	Partially correct
13	Correct	316 ms	16708 KB	Output is correct
14	Runtime error	816 ms	56900 KB	Memory limit exceeded
15	Correct	397 ms	22056 KB	Output is correct
16	Runtime error	783 ms	65536 KB	Execution killed with signal 9
17	Runtime error	779 ms	65540 KB	Execution killed with signal 9
18	Execution timed out	1066 ms	49232 KB	Time limit exceeded
19	Execution timed out	1108 ms	65540 KB	Time limit exceeded
20	Runtime error	766 ms	65540 KB	Execution killed with signal 9