Submission #580720

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
580720	2022-06-21T17:20:33 Z	vqpahmad	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	235 ms	13876 KB

jobs

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define all(a) a.begin(),a.end()
#define mod (ll)(10000007)
using namespace std;
const int mx = 1e6 + 15;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,d,m;
    cin >> n >> d >> m;
    vector<pair<int,int>> a(m);
    for (int i=0;i<m;i++){
        int x;
        cin >> x;
        a[i] = {x,i+1};
    }
    sort(all(a));
    int s = 0,e=m;
    int ans = m;
    while (s<=e){
        int mid = (s+e)/2;
        bool flag = 1;
        int i = 0;
        int day = 1;
        while (i<m){
            int up = upper_bound(all(a),make_pair(day,INT_MAX))-a.begin();
            int l = i;
            i = min(i+mid,up);
            if (l!=i){
                if (day-a[l+1].first > d) flag = 0;
            }
            day++;
            if (day==n+1) break;
        }
        if (i==m&&flag){
            ans = mid;
            e = mid - 1;
        }
        else s = mid + 1;
    }
    cout << ans << endl;
    int cur = 0;
    for (int i=1;i<=n;i++){
        int up = upper_bound(all(a),make_pair(i,INT_MAX))-a.begin();
        int t = cur+ans;
        t = min(m,t);
        if (cur!=m){
            for (;cur<t;cur++){
                if (a[cur].first>i) break;
                cout << a[cur].second << ' ';
            }
        }
        cout << 0 << endl;
    }
 
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:49:13: warning: unused variable 'up' [-Wunused-variable]
   49 |         int up = upper_bound(all(a),make_pair(i,INT_MAX))-a.begin();
      |             ^~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	1740 KB	Output is correct
2	Correct	18 ms	1628 KB	Output is correct
3	Correct	18 ms	1620 KB	Output is correct
4	Correct	17 ms	1668 KB	Output is correct
5	Correct	17 ms	1672 KB	Output is correct
6	Correct	17 ms	1620 KB	Output is correct
7	Correct	18 ms	1620 KB	Output is correct
8	Correct	16 ms	1620 KB	Output is correct
9	Correct	29 ms	1888 KB	Output is correct
10	Correct	30 ms	1868 KB	Output is correct
11	Correct	26 ms	1620 KB	Output is correct
12	Correct	52 ms	3168 KB	Output is correct
13	Correct	74 ms	4548 KB	Output is correct
14	Correct	129 ms	6136 KB	Output is correct
15	Correct	122 ms	7560 KB	Output is correct
16	Correct	186 ms	9112 KB	Output is correct
17	Correct	193 ms	10532 KB	Output is correct
18	Correct	213 ms	12112 KB	Output is correct
19	Correct	230 ms	13876 KB	Output is correct
20	Correct	235 ms	10548 KB	Output is correct