Submission #743580

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743580	2023-05-17T14:10:03 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	200 ms	13904 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<int> path;
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:45:17: warning: unused variable 'num' [-Wunused-variable]
   45 |             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	1744 KB	Output isn't correct
2	Incorrect	18 ms	1772 KB	Output isn't correct
3	Incorrect	18 ms	1744 KB	Output isn't correct
4	Incorrect	20 ms	1736 KB	Output isn't correct
5	Incorrect	19 ms	1744 KB	Output isn't correct
6	Incorrect	19 ms	1860 KB	Output isn't correct
7	Incorrect	19 ms	1832 KB	Output isn't correct
8	Incorrect	19 ms	1744 KB	Output isn't correct
9	Correct	23 ms	2008 KB	Output is correct
10	Correct	24 ms	1944 KB	Output is correct
11	Correct	26 ms	1736 KB	Output is correct
12	Correct	60 ms	3296 KB	Output is correct
13	Correct	66 ms	4728 KB	Output is correct
14	Correct	94 ms	6304 KB	Output is correct
15	Incorrect	107 ms	7668 KB	Output isn't correct
16	Correct	147 ms	9240 KB	Output is correct
17	Correct	200 ms	10680 KB	Output is correct
18	Correct	190 ms	12192 KB	Output is correct
19	Correct	194 ms	13904 KB	Output is correct
20	Correct	165 ms	10676 KB	Output is correct