Submission #744033

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
744033	2023-05-18T07:24:51 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	145 ms	16940 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	2508 KB	Output is correct
2	Correct	12 ms	2512 KB	Output is correct
3	Correct	13 ms	2484 KB	Output is correct
4	Correct	13 ms	2512 KB	Output is correct
5	Correct	12 ms	2512 KB	Output is correct
6	Correct	13 ms	2512 KB	Output is correct
7	Correct	13 ms	2468 KB	Output is correct
8	Correct	14 ms	2512 KB	Output is correct
9	Correct	19 ms	2436 KB	Output is correct
10	Correct	22 ms	2512 KB	Output is correct
11	Correct	15 ms	2512 KB	Output is correct
12	Correct	28 ms	4556 KB	Output is correct
13	Correct	43 ms	8584 KB	Output is correct
14	Correct	67 ms	8568 KB	Output is correct
15	Correct	76 ms	8648 KB	Output is correct
16	Correct	108 ms	16940 KB	Output is correct
17	Correct	119 ms	16820 KB	Output is correct
18	Correct	121 ms	16792 KB	Output is correct
19	Correct	145 ms	16824 KB	Output is correct
20	Correct	120 ms	16828 KB	Output is correct