Submission #744016

#	Time	Username	Problem	Language	Result	Execution time	Memory
744016		riodsa	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	287 ms	28192 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 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 (stderr)

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 / 100