oj.uz

Submission #562735

# Submission time Handle Problem Language Result Execution time Memory
562735 2022-05-15T06:51:19 Z Mridul Job Scheduling (CEOI12_jobs) C++14
0 / 100
 42 ms 65536 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define inf 1e18
#define ff first
#define ss second
#define mod 1000000007

bool helper(vector<pair<ll,ll>> &jobs,vector<vector<ll>> &ans,ll n, ll d, ll m, ll mid){

    /*
        Out here we need to count all the jobs that have frequency above
        0 and need to be processed with following mid machines.
    */

    auto temp = jobs;
    vector<ll> machines(mid, 0);
    // Initially all the machines are unoccupied.
    vector<ll> days(m+1,0);
    // we also need to maintain the no of days it took the job to complete.

    int i = 1;
    int j = 0;
    int count = 0;

    vector<vector<ll>> res;
    while(i<=m){

        count++;
        vector<ll> t;
        while(i<=m&&j<mid){


            if(temp[i].first>0){


                //reduce the frequency
                temp[i].first--;
                t.push_back(jobs[i].second);

                //update the counter of intital date
                //if not updated
                if(days[temp[i].second]==0){
                    days[temp[i].second]=count;
                }
                //update the res vector

                // if frequency ends, then update the total days
                if(temp[i].first==0){
                    if(count-days[temp[i].second]>d)
                        return false;
                    else
                        days[temp[i].second] = count - days[temp[i].second];
                    i++;
                }

                j++;

            }else{
                i++;
            }

        }
        t.push_back(0);
        res.push_back(t);
        j=j%mid;
    }

    
    if(count>n)
        return false;

    ans = res;

    return true;
}

void binarySearch(vector<pair<ll,ll>> &jobs, vector<vector<ll>> res,ll n, ll d, ll m){

    /*
        We need to find the minimum number of machines such
        that no job has to wait for more than 'd' days 
        since its commencement.
    */

    ll l = 1;
    ll r = m;
    ll ans;

    while(l<=r){
        ll mid = l + (r-l)/2;
        bool check = helper(jobs,res,n,d,m,mid);
        if(check){
            ans = mid;

            r = mid-1;
        }else{
            l = mid+1;
        }
    }

    cout<<ans<<endl;
    
    while(1ll*res.size()<n){
        res.push_back({0});
    }

    ll a = res.size();

    for(ll i = 0;i<a;i++){
        for(ll j = 0;j<res[i].size();j++){
            cout<<res[i][j]<<" ";
        }
        cout<<endl;
    }

}



void solve(){
    ll n,d,m;
    cin>>n>>d>>m;


    vector<pair<ll,ll>> jobs(m+1);
    vector<vector<ll>> ans;
    for(int i = 0;i<m;i++){
        ll x;
        cin>>x;
        jobs[x].first++;
        jobs[x].second = x;
    }

    sort(jobs.begin(),jobs.end());
    binarySearch(jobs,ans, n, d, m);
    
}  


int main()
{   
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    int t=1;
    //cin>>t;

    while(t--)
    {
        solve();
    }
    return 0;

}

Compilation message

jobs.cpp: In function 'void binarySearch(std::vector<std::pair<long long int, long long int> >&, std::vector<std::vector<long long int> >, long long int, long long int, long long int)':
jobs.cpp:105:25: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
  105 |     while(1ll*res.size()<n){
      |           ~~~~~~~~~~~~~~^~
jobs.cpp:112:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         for(ll j = 0;j<res[i].size();j++){
      |                      ~^~~~~~~~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:145:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:146:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 65536 KB Execution killed with signal 9
2 Runtime error 37 ms 65536 KB Execution killed with signal 9
3 Runtime error 33 ms 65536 KB Execution killed with signal 9
4 Runtime error 42 ms 65536 KB Execution killed with signal 9
5 Runtime error 35 ms 65536 KB Execution killed with signal 9
6 Runtime error 31 ms 65536 KB Execution killed with signal 9
7 Runtime error 33 ms 65536 KB Execution killed with signal 9
8 Runtime error 31 ms 65536 KB Execution killed with signal 9
9 Runtime error 33 ms 65536 KB Execution killed with signal 9
10 Runtime error 38 ms 65536 KB Execution killed with signal 9
11 Runtime error 36 ms 65536 KB Execution killed with signal 9
12 Runtime error 38 ms 65536 KB Execution killed with signal 9
13 Runtime error 34 ms 65536 KB Execution killed with signal 9
14 Runtime error 38 ms 65536 KB Execution killed with signal 9
15 Runtime error 32 ms 65536 KB Execution killed with signal 9
16 Runtime error 38 ms 65536 KB Execution killed with signal 9
17 Runtime error 36 ms 65536 KB Execution killed with signal 9
18 Runtime error 33 ms 65536 KB Execution killed with signal 9
19 Runtime error 33 ms 65536 KB Execution killed with signal 9
20 Runtime error 35 ms 65536 KB Execution killed with signal 9