oj.uz

Submission #850296

# Submission time Handle Problem Language Result Execution time Memory
850296 2023-09-16T09:39:23 Z srivatsav_kannan Job Scheduling (CEOI12_jobs) C++14
90 / 100
 151 ms 14984 KB 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <map>
#include <algorithm>
#include <numeric>
#include <stack>
#include <cstring>
#include <bitset>
#include <climits>
#include <valarray>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <complex>
//#include <bits/stdc++.h>
#define int long long int
#define double long double
#define endl '\n'
#define mod 1000000007
#define inf 2000000000000000000
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//#define ordered_set tree < int ,  null_type ,  less ,  rb_tree_tag ,  tree_order_statistics_node_update>
const int mxm = 1000001;
pair<int,int> ar[mxm];
int n,d,m;
bool f(int mid){
    int day = 1;
    int used = 0;
    for (int i = 0; i < m; i++){
        if (day > n) return false;
        used++;
        day = max(day, ar[i].first);
        if (day-ar[i].first > d || day > n) return false;
        if (used == mid) {
            used = 0;
            day++;
        }
    }
    return true;
}

void solve(){
    cin >> n >> d >> m;
    for (int i = 0; i < m; i++) {
        cin >> ar[i].first;
        ar[i].second = i+1;
    }
    sort(ar, ar+m);

    int l = 1, r = m;
    while (l < r) {
        int mid = (l+r)/2;
        if (f(mid)) r = mid;
        else l = mid+1;
    }
    cout << l << endl;
    
    for (int i = 1; i <= n; i++){
        cout << 0 << endl;
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//       freopen("swap.in", "r", stdin);
//       freopen("swap.out", "w", stdout);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2648 KB Output is correct
2 Correct 8 ms 2648 KB Output is correct
3 Correct 8 ms 2652 KB Output is correct
4 Correct 8 ms 2648 KB Output is correct
5 Correct 8 ms 2652 KB Output is correct
6 Correct 9 ms 2648 KB Output is correct
7 Correct 10 ms 2848 KB Output is correct
8 Correct 9 ms 2648 KB Output is correct
9 Correct 21 ms 2844 KB Output is correct
10 Correct 19 ms 2648 KB Output is correct
11 Correct 18 ms 2908 KB Output is correct
12 Correct 32 ms 4696 KB Output is correct
13 Correct 49 ms 6796 KB Output is correct
14 Correct 66 ms 6776 KB Output is correct
15 Incorrect 81 ms 8792 KB Output isn't correct
16 Correct 97 ms 10832 KB Output is correct
17 Correct 116 ms 12880 KB Output is correct
18 Correct 133 ms 14984 KB Output is correct
19 Incorrect 151 ms 14984 KB Output isn't correct
20 Correct 116 ms 12880 KB Output is correct