Submission #436689

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
436689	2021-06-24T18:40:24 Z	rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	70 / 100	768 ms	55896 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)

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

    for (int i=0; i<nums.size(); i++){
        
        if (day-nums[i].val>d){
            works=false;
            break;
        }
        day=max(day, nums[i].val);
        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;
        
        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:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i=0; i<nums.size(); i++){
      |                   ~^~~~~~~~~~~~
jobs.cpp:56:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             for (int j=0; j<req[i].size(); j++){
      |                           ~^~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:107:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for (int j=0; j<last[i].size(); j++){
      |                       ~^~~~~~~~~~~~~~~

Subtask #1

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	10168 KB	Output is correct
2	Correct	82 ms	10176 KB	Output is correct
3	Correct	90 ms	10176 KB	Output is correct
4	Correct	91 ms	10168 KB	Output is correct
5	Correct	82 ms	10068 KB	Output is correct
6	Correct	85 ms	10184 KB	Output is correct
7	Correct	82 ms	10076 KB	Output is correct
8	Correct	88 ms	10100 KB	Output is correct
9	Correct	236 ms	9912 KB	Output is correct
10	Correct	223 ms	9932 KB	Output is correct
11	Correct	89 ms	10492 KB	Output is correct
12	Correct	142 ms	15708 KB	Output is correct
13	Correct	211 ms	21040 KB	Output is correct
14	Correct	339 ms	26784 KB	Output is correct
15	Runtime error	340 ms	34324 KB	Memory limit exceeded
16	Runtime error	468 ms	39708 KB	Memory limit exceeded
17	Runtime error	543 ms	46848 KB	Memory limit exceeded
18	Runtime error	556 ms	50000 KB	Memory limit exceeded
19	Runtime error	768 ms	55896 KB	Memory limit exceeded
20	Runtime error	552 ms	46840 KB	Memory limit exceeded