Submission #436069

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
436069	2021-06-24T07:34:58 Z	rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	40 / 100	509 ms	42376 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];
vector<ll> last[MN];

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

    bool works=true;
    ll day=1;
    ll left=x;

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

    if (works){
        for (int i=0; i<MN; i++){
            last[i].clear();
            for (int j=0; j<req[i].size(); j++){
                last[i].pb(req[i][j]);
            }
        }
    }

    for (int i=0; i<MN; i++){
        req[i].clear();
    }

    return works;

}

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(1, INT_MAX);

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





}

Compilation message

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

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	35 ms	7172 KB	Output isn't correct
2	Incorrect	35 ms	7192 KB	Output isn't correct
3	Incorrect	34 ms	7112 KB	Output isn't correct
4	Incorrect	35 ms	7204 KB	Output isn't correct
5	Incorrect	35 ms	7088 KB	Output isn't correct
6	Incorrect	34 ms	7112 KB	Output isn't correct
7	Incorrect	35 ms	7112 KB	Output isn't correct
8	Incorrect	34 ms	7144 KB	Output isn't correct
9	Correct	199 ms	9272 KB	Output is correct
10	Correct	204 ms	9344 KB	Output is correct
11	Correct	45 ms	9140 KB	Output is correct
12	Correct	79 ms	13528 KB	Output is correct
13	Correct	143 ms	19696 KB	Output is correct
14	Correct	205 ms	24476 KB	Output is correct
15	Correct	196 ms	24220 KB	Output is correct
16	Correct	305 ms	31636 KB	Output is correct
17	Runtime error	391 ms	42368 KB	Memory limit exceeded
18	Runtime error	348 ms	39352 KB	Memory limit exceeded
19	Runtime error	509 ms	41740 KB	Memory limit exceeded
20	Runtime error	356 ms	42376 KB	Memory limit exceeded