oj.uz

Submission #916222

# Submission time Handle Problem Language Result Execution time Memory
916222 2024-01-25T13:51:17 Z a_l_i_r_e_z_a Job Scheduling (CEOI12_jobs) C++17
94 / 100
 225 ms 23556 KB 
// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())

const int maxn = 1e5 + 5, maxm = 1e6 + 5;
const int inf = 1e9 + 7;
int n, d, m;
pii a[maxm];
vector<int> vec[maxn];

bool check(int k){
    int cur = 0;
    for(int i = 1; i <= n; i++){
        vec[i].clear();
        int cnt = 0;
        if(a[cur].F + d < i) return 0;
        while(cnt < k && cur < m && a[cur].F <= i){
            vec[i].pb(a[cur++].S);
            cnt++;
        }
        if(cur == m) break;
    }
    if(cur != m) return 0;
    return 1;
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> d >> m;
    for(int i = 0; i < m; i++){
        cin >> a[i].F;
        a[i].S = i + 1;
    }
    sort(a, a + m);
    int l = 0, r = m + 1;
    while(r - l > 1){
        int mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid;
    }
    cout << l + 1 << '\n';
    check(l + 1);
    for(int i = 1; i <= n; i++){
        for(auto u: vec[i]) cout << u << ' ';
        cout << 0 << '\n';
    }

    return 0;
}

Subtask #1
94.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5980 KB Output is correct
2 Correct 16 ms 5980 KB Output is correct
3 Correct 15 ms 5980 KB Output is correct
4 Correct 14 ms 5976 KB Output is correct
5 Correct 16 ms 6140 KB Output is correct
6 Correct 17 ms 5980 KB Output is correct
7 Correct 17 ms 5976 KB Output is correct
8 Correct 17 ms 6232 KB Output is correct
9 Correct 31 ms 6288 KB Output is correct
10 Correct 27 ms 6228 KB Output is correct
11 Correct 23 ms 5972 KB Output is correct
12 Correct 46 ms 7760 KB Output is correct
13 Correct 65 ms 11800 KB Output is correct
14 Correct 98 ms 13936 KB Output is correct
15 Correct 109 ms 14928 KB Output is correct
16 Correct 154 ms 19028 KB Output is correct
17 Partially correct 185 ms 22412 KB Partially correct
18 Correct 185 ms 21528 KB Output is correct
19 Correct 225 ms 23556 KB Output is correct
20 Partially correct 178 ms 22352 KB Partially correct