Submission #742957

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
742957	2023-05-17T06:57:30 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	10 / 100	1000 ms	65536 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;
priority_queue<job> pq;
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;
        pq.push({x,i});
    }
//    while(!pq.empty())
//    {
//        cout << pq.top().dline << " " << pq.top().idx << '\n';
//        pq.pop();
//    }
    int l = 1,r = n;
    while(l<=r)
    {
        priority_queue<job> tmp = pq;
        int mid = (l+r)/2;
//        cout << "mid = " << mid << '\n';
        bool all = true;
        bool cant = false;
        int cnt=0;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=mid;++j)
            {
//                cout << "day = " << i << " deadline now " << tmp.top().dline << '\n';
                if(i > tmp.top().dline)
                {
                    cant = true;
                    break;
                }
                if(!tmp.empty()) tmp.pop();
            }
            if(cant) break;
        }
        if((!cant) && tmp.empty())
        {
            r = mid-1;
            ans = mid;
        }
        else l = mid+1;
//        cout << "\n\n";
    }
    cout << ans << '\n';
    int d = 0;
    while(!pq.empty())
    {
        for(int i=1;i<=ans;++i)
        {
            cout << pq.top().idx << " ";
            pq.pop();
        }
        ++d;
        cout << "0\n";
    }
    while(d < n)
    {
        cout << "0\n";
        d++;
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:42:14: warning: unused variable 'all' [-Wunused-variable]
   42 |         bool all = true;
      |              ^~~
jobs.cpp:44:13: warning: unused variable 'cnt' [-Wunused-variable]
   44 |         int cnt=0;
      |             ^~~

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1068 ms	65536 KB	Time limit exceeded
2	Execution timed out	1070 ms	65536 KB	Time limit exceeded
3	Execution timed out	1066 ms	65536 KB	Time limit exceeded
4	Execution timed out	1076 ms	65536 KB	Time limit exceeded
5	Execution timed out	1073 ms	65536 KB	Time limit exceeded
6	Execution timed out	1069 ms	65536 KB	Time limit exceeded
7	Execution timed out	1082 ms	65536 KB	Time limit exceeded
8	Execution timed out	1081 ms	65536 KB	Time limit exceeded
9	Execution timed out	1025 ms	65536 KB	Time limit exceeded
10	Execution timed out	1083 ms	65536 KB	Time limit exceeded
11	Execution timed out	1077 ms	65536 KB	Time limit exceeded
12	Correct	291 ms	5364 KB	Output is correct
13	Execution timed out	1038 ms	59588 KB	Time limit exceeded
14	Correct	954 ms	10616 KB	Output is correct
15	Execution timed out	1048 ms	32728 KB	Time limit exceeded
16	Execution timed out	1034 ms	11084 KB	Time limit exceeded
17	Execution timed out	1045 ms	12692 KB	Time limit exceeded
18	Execution timed out	1029 ms	14224 KB	Time limit exceeded
19	Execution timed out	1026 ms	15712 KB	Time limit exceeded
20	Execution timed out	1002 ms	12596 KB	Time limit exceeded