Submission #743578

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743578	2023-05-17T14:09:23 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	201 ms	14152 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 = n;
    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	17 ms	2128 KB	Output isn't correct
2	Incorrect	16 ms	2080 KB	Output isn't correct
3	Incorrect	16 ms	2096 KB	Output isn't correct
4	Incorrect	17 ms	1996 KB	Output isn't correct
5	Incorrect	17 ms	2072 KB	Output isn't correct
6	Incorrect	16 ms	2044 KB	Output isn't correct
7	Incorrect	21 ms	2000 KB	Output isn't correct
8	Incorrect	17 ms	2080 KB	Output isn't correct
9	Correct	21 ms	2236 KB	Output is correct
10	Correct	21 ms	2188 KB	Output is correct
11	Correct	21 ms	2020 KB	Output is correct
12	Correct	40 ms	3548 KB	Output is correct
13	Correct	60 ms	5040 KB	Output is correct
14	Correct	87 ms	6508 KB	Output is correct
15	Incorrect	97 ms	7960 KB	Output isn't correct
16	Correct	145 ms	9496 KB	Output is correct
17	Correct	152 ms	10952 KB	Output is correct
18	Correct	163 ms	12496 KB	Output is correct
19	Correct	201 ms	14152 KB	Output is correct
20	Correct	149 ms	11000 KB	Output is correct