oj.uz

답안 #562733

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
562733 2022-05-15T06:47:17 Z Mridul Job Scheduling (CEOI12_jobs) C++14
0 / 100
 623 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(res.size()<n){
        res.push_back({0});
    }

    for(int i = 0;i<res.size();i++){
        for(int 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()
{   
    

    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:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  105 |     while(res.size()<n){
      |           ~~~~~~~~~~^~
jobs.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i = 0;i<res.size();i++){
      |                   ~^~~~~~~~~~~
jobs.cpp:110:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(int j = 0;j<res[i].size();j++){
      |                       ~^~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 7296 KB Expected EOLN
2 Incorrect 56 ms 7244 KB Expected EOLN
3 Incorrect 55 ms 7324 KB Expected EOLN
4 Incorrect 51 ms 7292 KB Expected EOLN
5 Incorrect 50 ms 7344 KB Expected EOLN
6 Incorrect 51 ms 7332 KB Expected EOLN
7 Incorrect 54 ms 7432 KB Expected EOLN
8 Incorrect 65 ms 7320 KB Expected EOLN
9 Incorrect 171 ms 11240 KB Output isn't correct
10 Incorrect 180 ms 11244 KB Output isn't correct
11 Incorrect 71 ms 7844 KB Output isn't correct
12 Incorrect 114 ms 15504 KB Expected EOLN
13 Incorrect 160 ms 22912 KB Output isn't correct
14 Incorrect 277 ms 31548 KB Expected EOLN
15 Runtime error 251 ms 37948 KB Memory limit exceeded
16 Runtime error 387 ms 46764 KB Memory limit exceeded
17 Runtime error 494 ms 54700 KB Memory limit exceeded
18 Runtime error 466 ms 61424 KB Memory limit exceeded
19 Runtime error 623 ms 65536 KB Memory limit exceeded
20 Runtime error 470 ms 54824 KB Memory limit exceeded