Submission #743595

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743595	2023-05-17T14:17:14 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	193 ms	13864 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

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	18 ms	1736 KB	Output isn't correct
2	Incorrect	21 ms	1816 KB	Output isn't correct
3	Incorrect	19 ms	1744 KB	Output isn't correct
4	Incorrect	27 ms	1852 KB	Output isn't correct
5	Incorrect	17 ms	1744 KB	Output isn't correct
6	Incorrect	21 ms	1872 KB	Output isn't correct
7	Incorrect	16 ms	1744 KB	Output isn't correct
8	Incorrect	17 ms	1776 KB	Output isn't correct
9	Correct	24 ms	2032 KB	Output is correct
10	Correct	23 ms	2000 KB	Output is correct
11	Correct	21 ms	1856 KB	Output is correct
12	Correct	50 ms	3292 KB	Output is correct
13	Correct	63 ms	4716 KB	Output is correct
14	Correct	99 ms	6268 KB	Output is correct
15	Incorrect	107 ms	7692 KB	Output isn't correct
16	Correct	139 ms	9228 KB	Output is correct
17	Correct	167 ms	10884 KB	Output is correct
18	Correct	193 ms	12204 KB	Output is correct
19	Correct	188 ms	13864 KB	Output is correct
20	Correct	168 ms	10668 KB	Output is correct