Submission #436061

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
436061	2021-06-24T07:20:01 Z	rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	30 / 100	618 ms	56648 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++){
        day=max(nums[i].val, day);
        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(0, 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:58:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for (int j=0; j<req[i].size(); j++){
      |                           ~^~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:109:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for (int j=0; j<last[i].size(); j++){
      |                       ~^~~~~~~~~~~~~~~

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	41 ms	7112 KB	Output isn't correct
2	Incorrect	36 ms	7112 KB	Output isn't correct
3	Incorrect	39 ms	7160 KB	Output isn't correct
4	Incorrect	35 ms	7112 KB	Output isn't correct
5	Incorrect	34 ms	7112 KB	Output isn't correct
6	Incorrect	34 ms	7108 KB	Output isn't correct
7	Incorrect	35 ms	7112 KB	Output isn't correct
8	Incorrect	42 ms	7112 KB	Output isn't correct
9	Correct	207 ms	9776 KB	Output is correct
10	Correct	205 ms	9908 KB	Output is correct
11	Correct	49 ms	10300 KB	Output is correct
12	Correct	93 ms	14796 KB	Output is correct
13	Correct	131 ms	20824 KB	Output is correct
14	Correct	247 ms	27944 KB	Output is correct
15	Runtime error	244 ms	33576 KB	Memory limit exceeded
16	Runtime error	337 ms	41268 KB	Memory limit exceeded
17	Runtime error	397 ms	47756 KB	Memory limit exceeded
18	Runtime error	396 ms	46272 KB	Memory limit exceeded
19	Runtime error	618 ms	56648 KB	Memory limit exceeded
20	Runtime error	385 ms	47668 KB	Memory limit exceeded