Submission #436690

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
436690	2021-06-24T18:41:49 Z	rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	70 / 100	774 ms	57252 KB

jobs

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

typedef long long ll;
const int MN=2e5+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	101 ms	14772 KB	Output is correct
2	Correct	104 ms	14820 KB	Output is correct
3	Correct	122 ms	14792 KB	Output is correct
4	Correct	102 ms	14776 KB	Output is correct
5	Correct	100 ms	14880 KB	Output is correct
6	Correct	102 ms	14872 KB	Output is correct
7	Correct	123 ms	14780 KB	Output is correct
8	Correct	101 ms	14772 KB	Output is correct
9	Correct	244 ms	14628 KB	Output is correct
10	Correct	281 ms	14752 KB	Output is correct
11	Correct	104 ms	14976 KB	Output is correct
12	Correct	165 ms	20492 KB	Output is correct
13	Correct	246 ms	25796 KB	Output is correct
14	Correct	340 ms	31344 KB	Output is correct
15	Runtime error	370 ms	37908 KB	Memory limit exceeded
16	Runtime error	472 ms	41384 KB	Memory limit exceeded
17	Runtime error	565 ms	48272 KB	Memory limit exceeded
18	Runtime error	559 ms	51644 KB	Memory limit exceeded
19	Runtime error	774 ms	57252 KB	Memory limit exceeded
20	Runtime error	545 ms	48140 KB	Memory limit exceeded