Submission #744011

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
744011	2023-05-18T07:11:55 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	230 ms	28032 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 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].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:13:33: warning: statement has no effect [-Wunused-value]
   13 |         if(give != x.give) give < x.give;
      |                            ~~~~~^~~~~~~~
jobs.cpp: In function 'int main()':
jobs.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   24 |     for(int i=1;i<=m;++i)
      |                 ~^~~
jobs.cpp:28:30: warning: narrowing conversion of 'i' from 'int' to 'long long unsigned int' [-Wnarrowing]
   28 |         vec.push_back({x+d,x,i});
      |                              ^
jobs.cpp:43:22: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   43 |         for(int i=0;i<m;++i)
      |                     ~^~
jobs.cpp:45:16: warning: unused variable 'num' [-Wunused-variable]
   45 |             ll num = day;
      |                ^~~
jobs.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   69 |     for(int i=0;i<m;++i)
      |                 ~^~

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	18 ms	3528 KB	Output isn't correct
2	Incorrect	19 ms	3528 KB	Output isn't correct
3	Incorrect	20 ms	3528 KB	Output isn't correct
4	Incorrect	19 ms	3528 KB	Output isn't correct
5	Incorrect	21 ms	3464 KB	Output isn't correct
6	Incorrect	20 ms	3652 KB	Output isn't correct
7	Incorrect	21 ms	3528 KB	Output isn't correct
8	Incorrect	21 ms	3448 KB	Output isn't correct
9	Correct	22 ms	3528 KB	Output is correct
10	Correct	25 ms	3572 KB	Output is correct
11	Correct	24 ms	3520 KB	Output is correct
12	Correct	60 ms	6596 KB	Output is correct
13	Correct	77 ms	12692 KB	Output is correct
14	Correct	107 ms	12772 KB	Output is correct
15	Incorrect	123 ms	15512 KB	Output isn't correct
16	Correct	167 ms	25012 KB	Output is correct
17	Correct	201 ms	24964 KB	Output is correct
18	Correct	205 ms	25028 KB	Output is correct
19	Correct	230 ms	28032 KB	Output is correct
20	Correct	212 ms	25004 KB	Output is correct