Submission #436689

#	Time	Username	Problem	Language	Result	Execution time	Memory
436689		rzirvi1665	Job Scheduling (CEOI12_jobs)	C++14	70 / 100	768 ms	55896 KiB

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 (stderr)

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 / 100