Submission #744016

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
744016	2023-05-18T07:12:52 Z	riodsa	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	287 ms	28192 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	21 ms	3656 KB	Output isn't correct
2	Incorrect	24 ms	3656 KB	Output isn't correct
3	Incorrect	22 ms	3708 KB	Output isn't correct
4	Incorrect	21 ms	3656 KB	Output isn't correct
5	Incorrect	20 ms	3648 KB	Output isn't correct
6	Incorrect	21 ms	3644 KB	Output isn't correct
7	Incorrect	25 ms	3656 KB	Output isn't correct
8	Incorrect	25 ms	3656 KB	Output isn't correct
9	Correct	25 ms	3680 KB	Output is correct
10	Correct	32 ms	3660 KB	Output is correct
11	Correct	28 ms	3784 KB	Output is correct
12	Correct	59 ms	6884 KB	Output is correct
13	Correct	92 ms	12940 KB	Output is correct
14	Correct	128 ms	12968 KB	Output is correct
15	Incorrect	151 ms	15804 KB	Output isn't correct
16	Correct	187 ms	25308 KB	Output is correct
17	Correct	226 ms	25336 KB	Output is correct
18	Correct	240 ms	25236 KB	Output is correct
19	Correct	287 ms	28192 KB	Output is correct
20	Correct	244 ms	25272 KB	Output is correct