Submission #744489

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
744489	2023-05-18T15:44:55 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	232 ms	28112 KB

jobs

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

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

struct job
{
    ll dline,give,idx;

    bool operator <(const job &x)const{
        if(give != x.give) give < x.give;
        return dline < x.dline;
    }
};

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+d,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;
        ll day=1,cb = 0;
        bool can = true;
//        cout << "mid = " << mid << '\n';
        for(int i=0;i<m;++i)
        {
            ll num = day;
//            cout << "day : " << num << " this job death line : " << vec[i].dline << '\n';
            if(day < vec[i].give)
            {
                day = vec[i].give;
                cb = 0;
            }
            if(day > vec[i].dline)
            {
                can = false;
                break;
            }
            ++cb;
            if(cb == mid)
            {
                ++day;
                cb = 0;
            }
        }
        if(can)
        {
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
//        cout << "\n\n";
    }
    cout << ans << '\n';
    ll cnt = 0;
    for(int i=0;i<m;++i)
    {
        if(vec[i].dline != 0) cout << vec[i].idx << " ";
        if((i+1)%ans == 0)
        {
            cout << "0\n";
            ++cnt;
        }
    }
    while(cnt < n)
    {
        cout << "0\n";
        cnt++;
    }
    return 0;
}

Compilation message

jobs.cpp: In member function 'bool job::operator<(const job&) const':
jobs.cpp:14:33: warning: statement has no effect [-Wunused-value]
   14 |         if(give != x.give) give < x.give;
      |                            ~~~~~^~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   25 |     for(int i=1;i<=m;++i)
      |                 ~^~~
jobs.cpp:29:30: warning: narrowing conversion of 'i' from 'int' to 'long long unsigned int' [-Wnarrowing]
   29 |         vec.push_back({x+d,x,i});
      |                              ^
jobs.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   44 |         for(int i=0;i<m;++i)
      |                     ~^~
jobs.cpp:46:16: warning: unused variable 'num' [-Wunused-variable]
   46 |             ll num = day;
      |                ^~~
jobs.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   75 |     for(int i=0;i<m;++i)
      |                 ~^~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	3528 KB	Output is correct
2	Correct	21 ms	3432 KB	Output is correct
3	Correct	20 ms	3528 KB	Output is correct
4	Correct	21 ms	3528 KB	Output is correct
5	Correct	20 ms	3528 KB	Output is correct
6	Correct	20 ms	3528 KB	Output is correct
7	Correct	20 ms	3528 KB	Output is correct
8	Correct	20 ms	3528 KB	Output is correct
9	Correct	23 ms	3564 KB	Output is correct
10	Correct	32 ms	3528 KB	Output is correct
11	Correct	27 ms	3512 KB	Output is correct
12	Correct	53 ms	6604 KB	Output is correct
13	Correct	82 ms	12700 KB	Output is correct
14	Correct	109 ms	12740 KB	Output is correct
15	Correct	134 ms	15572 KB	Output is correct
16	Correct	171 ms	25008 KB	Output is correct
17	Correct	217 ms	25068 KB	Output is correct
18	Correct	222 ms	24976 KB	Output is correct
19	Correct	232 ms	28112 KB	Output is correct
20	Correct	194 ms	24988 KB	Output is correct