Submission #743598

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743598	2023-05-17T14:18:07 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	194 ms	20924 KB

jobs

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

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

struct job
{
    ll dline,idx;

    bool operator <(const job &x)const{
        if(dline != x.dline) 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;
        x += d;
        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;
        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 function 'int main()':
jobs.cpp:45:16: warning: unused variable 'num' [-Wunused-variable]
   45 |             ll num = day;
      |                ^~~
jobs.cpp: In member function 'bool job::operator<(const job&) const':
jobs.cpp:14:5: warning: control reaches end of non-void function [-Wreturn-type]
   14 |     }
      |     ^

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	17 ms	2544 KB	Output isn't correct
2	Incorrect	17 ms	2544 KB	Output isn't correct
3	Incorrect	18 ms	2616 KB	Output isn't correct
4	Incorrect	17 ms	2636 KB	Output isn't correct
5	Incorrect	16 ms	2544 KB	Output isn't correct
6	Incorrect	18 ms	2596 KB	Output isn't correct
7	Incorrect	17 ms	2636 KB	Output isn't correct
8	Incorrect	18 ms	2548 KB	Output isn't correct
9	Correct	21 ms	2764 KB	Output is correct
10	Correct	23 ms	2760 KB	Output is correct
11	Correct	22 ms	2512 KB	Output is correct
12	Correct	45 ms	4948 KB	Output is correct
13	Correct	66 ms	8652 KB	Output is correct
14	Correct	100 ms	9384 KB	Output is correct
15	Incorrect	110 ms	11616 KB	Output isn't correct
16	Correct	146 ms	16824 KB	Output is correct
17	Correct	180 ms	16824 KB	Output is correct
18	Correct	177 ms	18456 KB	Output is correct
19	Correct	194 ms	20924 KB	Output is correct
20	Correct	168 ms	16756 KB	Output is correct