oj.uz

Submission #916224

# Submission time Handle Problem Language Result Execution time Memory
916224 2024-01-25T13:57:59 Z a_l_i_r_e_z_a Job Scheduling (CEOI12_jobs) C++17
100 / 100
 217 ms 20052 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;
        while(cnt < k && cur < m && a[cur].F <= i && a[cur].F + d >= i){
            vec[i].pb(a[cur].S);
            cnt++;
            cur++;
        }
    }
    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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5756 KB Output is correct
2 Correct 17 ms 5720 KB Output is correct
3 Correct 15 ms 5724 KB Output is correct
4 Correct 20 ms 5724 KB Output is correct
5 Correct 15 ms 5720 KB Output is correct
6 Correct 15 ms 5724 KB Output is correct
7 Correct 17 ms 5724 KB Output is correct
8 Correct 17 ms 5724 KB Output is correct
9 Correct 30 ms 5980 KB Output is correct
10 Correct 30 ms 5976 KB Output is correct
11 Correct 23 ms 5724 KB Output is correct
12 Correct 51 ms 6992 KB Output is correct
13 Correct 71 ms 10628 KB Output is correct
14 Correct 101 ms 12120 KB Output is correct
15 Correct 115 ms 13008 KB Output is correct
16 Correct 153 ms 16208 KB Output is correct
17 Correct 181 ms 19068 KB Output is correct
18 Correct 217 ms 18560 KB Output is correct
19 Correct 213 ms 20052 KB Output is correct
20 Correct 169 ms 18992 KB Output is correct