Submission #743576

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743576	2023-05-17T14:08:08 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	276 ms	13832 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;
        return idx < x.idx;
    }
};

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:46:17: warning: unused variable 'num' [-Wunused-variable]
   46 |             int num = day;
      |                 ^~~

Subtask #1

55.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	16 ms	1744 KB	Output isn't correct
2	Incorrect	19 ms	1796 KB	Output isn't correct
3	Incorrect	18 ms	1776 KB	Output isn't correct
4	Incorrect	18 ms	1836 KB	Output isn't correct
5	Incorrect	26 ms	1808 KB	Output isn't correct
6	Incorrect	22 ms	1744 KB	Output isn't correct
7	Incorrect	16 ms	1768 KB	Output isn't correct
8	Incorrect	23 ms	1760 KB	Output isn't correct
9	Correct	30 ms	2132 KB	Output is correct
10	Correct	29 ms	2000 KB	Output is correct
11	Correct	32 ms	1756 KB	Output is correct
12	Correct	67 ms	3304 KB	Output is correct
13	Correct	81 ms	4772 KB	Output is correct
14	Correct	118 ms	6268 KB	Output is correct
15	Incorrect	127 ms	7748 KB	Output isn't correct
16	Correct	184 ms	9236 KB	Output is correct
17	Correct	192 ms	10644 KB	Output is correct
18	Correct	218 ms	12244 KB	Output is correct
19	Correct	276 ms	13832 KB	Output is correct
20	Correct	216 ms	10760 KB	Output is correct