oj.uz

Submission #954715

# Submission time Handle Problem Language Result Execution time Memory
954715 2024-03-28T12:13:42 Z daviedu Job Scheduling (CEOI12_jobs) C++17
100 / 100
 206 ms 13888 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ll long long
 
struct P{
    ll x, y;
};
 
void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }
 
 
 
signed main(){
    fastio;
    int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> arr (m);
    for (int i=1, x; i<=m; i++){
        cin >> x;
        arr[i-1] = {x, i};
    }
    sort(all(arr));

    int l=1, r=m, pcs=1;
    while (l<=r){
        int mid = l + (r-l)/2;

        bool late = false;
        int j=0;
        for (int i=0; i<n; i++){
            for (int k=0; k<mid && j<m && i+1>=arr[j].first; k++, j++){
                if (i+1 > arr[j].first+d){
                    late = true;
                    break;
                }
            }
        }

        if (j == m && !late){
            r = mid-1;
            pcs = mid;
        }
        else l = mid+1;
    }

    cout << pcs << '\n';
    int j=0;
    for (int i=0; i<n; i++){
        for (int k=0; k<pcs && j<m && i+1>=arr[j].first; k++, j++){
            cout << arr[j].second << ' ';
        }
        cout << 0 << '\n';
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1760 KB Output is correct
2 Correct 15 ms 1628 KB Output is correct
3 Correct 15 ms 1624 KB Output is correct
4 Correct 15 ms 1628 KB Output is correct
5 Correct 16 ms 1624 KB Output is correct
6 Correct 15 ms 1624 KB Output is correct
7 Correct 15 ms 1624 KB Output is correct
8 Correct 15 ms 1628 KB Output is correct
9 Correct 27 ms 1880 KB Output is correct
10 Correct 26 ms 2008 KB Output is correct
11 Correct 21 ms 1628 KB Output is correct
12 Correct 43 ms 3156 KB Output is correct
13 Correct 70 ms 4692 KB Output is correct
14 Correct 90 ms 6152 KB Output is correct
15 Correct 113 ms 7804 KB Output is correct
16 Correct 134 ms 9044 KB Output is correct
17 Correct 154 ms 10536 KB Output is correct
18 Correct 177 ms 12112 KB Output is correct
19 Correct 206 ms 13888 KB Output is correct
20 Correct 157 ms 10580 KB Output is correct