Submission #743594

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743594	2023-05-17T14:16:52 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	30 / 100	191 ms	13852 KB

jobs

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

const int N = 1e5+1;
int n,d,m;

struct job
{
    int dline,idx;

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

int 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)
    {
        int 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();
//    }
    int l = 1,r = 1e9+7;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int day=1,cb = 0;
        bool can = true;
//        cout << "mid = " << mid << '\n';
        for(int i=0;i<m;++i)
        {
            int 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';
    int 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:44:17: warning: unused variable 'num' [-Wunused-variable]
   44 |             int num = day;
      |                 ^~~
jobs.cpp: In member function 'bool job::operator<(const job&) const':
jobs.cpp:13:5: warning: control reaches end of non-void function [-Wreturn-type]
   13 |     }
      |     ^

Subtask #1

30.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	17 ms	1744 KB	Output isn't correct
2	Incorrect	17 ms	1832 KB	Output isn't correct
3	Incorrect	19 ms	1776 KB	Output isn't correct
4	Incorrect	17 ms	1800 KB	Output isn't correct
5	Incorrect	16 ms	1784 KB	Output isn't correct
6	Incorrect	17 ms	1744 KB	Output isn't correct
7	Incorrect	17 ms	1768 KB	Output isn't correct
8	Incorrect	17 ms	1764 KB	Output isn't correct
9	Incorrect	21 ms	1988 KB	Output isn't correct
10	Incorrect	25 ms	2088 KB	Output isn't correct
11	Correct	21 ms	1852 KB	Output is correct
12	Incorrect	46 ms	3268 KB	Output isn't correct
13	Correct	63 ms	4788 KB	Output is correct
14	Incorrect	96 ms	6232 KB	Output isn't correct
15	Incorrect	110 ms	7756 KB	Output isn't correct
16	Correct	141 ms	9260 KB	Output is correct
17	Correct	176 ms	10704 KB	Output is correct
18	Correct	167 ms	12220 KB	Output is correct
19	Incorrect	191 ms	13852 KB	Output isn't correct
20	Correct	165 ms	10660 KB	Output is correct