Submission #436063

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
436063	2021-06-24T07:23:40 Z	rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	30 / 100	596 ms	52204 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(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: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	37 ms	7144 KB	Output isn't correct
2	Incorrect	33 ms	7212 KB	Output isn't correct
3	Incorrect	33 ms	7112 KB	Output isn't correct
4	Incorrect	35 ms	7140 KB	Output isn't correct
5	Incorrect	34 ms	7112 KB	Output isn't correct
6	Incorrect	36 ms	7112 KB	Output isn't correct
7	Incorrect	36 ms	7112 KB	Output isn't correct
8	Incorrect	41 ms	7328 KB	Output isn't correct
9	Correct	215 ms	9968 KB	Output is correct
10	Correct	242 ms	9872 KB	Output is correct
11	Correct	48 ms	9908 KB	Output is correct
12	Correct	87 ms	14900 KB	Output is correct
13	Correct	143 ms	20824 KB	Output is correct
14	Correct	249 ms	26544 KB	Output is correct
15	Runtime error	241 ms	33684 KB	Memory limit exceeded
16	Runtime error	371 ms	36624 KB	Memory limit exceeded
17	Runtime error	407 ms	43492 KB	Memory limit exceeded
18	Runtime error	435 ms	45220 KB	Memory limit exceeded
19	Runtime error	596 ms	52204 KB	Memory limit exceeded
20	Runtime error	398 ms	43536 KB	Memory limit exceeded