Submission #744033

#	Time	Username	Problem	Language	Result	Execution time	Memory
744033		vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	145 ms	16940 KiB

jobs

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

#define ll unsigned long long
const int N = 1e5+1;
ll n,d,m;

struct job
{
    ll give,idx;

    bool operator <(const job &x)const{
        return give < x.give;
    }
};

ll ans;
vector<job> vec;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> d >> m;
    for(int i=1;i<=m;++i)
    {
        ll x;
        cin >> x;
        vec.push_back({x,i});
    }
    sort(vec.begin(),vec.end());
//    while(!pq.empty())
//    {
//        cout << pq.top().dline << " " << pq.top().idx << '\n';
//        pq.pop();
//    }
    ll l = 1,r = 1e9+7;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        int j = 0;
        for(int i = 1;i<=n;++i)
        {
            int cnt = 0;
            while(j <= m && vec[j].give <= i && i-vec[j].give <= d && cnt < mid)
            {
                ++cnt;
                ++j;
            }
        }
        if(j == m)
        {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
//        cout << "\n\n";
    }
    cout << ans << '\n';
    for(int i=1;i<=n;++i) cout << "0\n";
    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   23 |     for(int i=1;i<=m;++i)
      |                 ~^~~
jobs.cpp:27:26: warning: narrowing conversion of 'i' from 'int' to 'long long unsigned int' [-Wnarrowing]
   27 |         vec.push_back({x,i});
      |                          ^
jobs.cpp:40:24: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   40 |         for(int i = 1;i<=n;++i)
      |                       ~^~~
jobs.cpp:43:21: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   43 |             while(j <= m && vec[j].give <= i && i-vec[j].give <= d && cnt < mid)
      |                   ~~^~~~
jobs.cpp:43:41: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   43 |             while(j <= m && vec[j].give <= i && i-vec[j].give <= d && cnt < mid)
jobs.cpp:43:75: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   43 |             while(j <= m && vec[j].give <= i && i-vec[j].give <= d && cnt < mid)
      |                                                                       ~~~~^~~~~
jobs.cpp:49:14: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   49 |         if(j == m)
      |            ~~^~~~
jobs.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   58 |     for(int i=1;i<=n;++i) cout << "0\n";
      |                 ~^~~

• Subtask 1: 100 / 100