oj.uz

Submission #1087586

# Submission time Handle Problem Language Result Execution time Memory
1087586 2024-09-13T02:01:30 Z Rafael_Augusto Job Scheduling (CEOI12_jobs) C++17
100 / 100
 645 ms 19168 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define fall(i, n) for(int i=0; i<n; i++)

typedef long long ll;
typedef pair<int, int> pii;

int n, d, m;
vector<pii> v;

bool f(int c){
    int id=c;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    fall(i, c) pq.push(v[i].f);
    
    while(id < m){
        int t = pq.top()+1;
        
        if(t - v[id].f > d) return 0;
        
        pq.pop(), pq.push(max(t, v[id].f)), id++;
    }
    
    return 1;
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> d >> m;
    
    v=vector<pii>(m);
    
    fall(i, m){
        cin >> v[i].f;
        
        v[i].s = i+1;
    }
    
    sort(v.begin(), v.end());
    
    int ini=1, fim = m;
    
    while(ini < fim){
        ll mid = (ini+fim)/2;
        
        if(f(mid)) fim = mid;
        else ini = mid+1;
    }
    
    cout << fim << "\n";
    
    int id=0;
    
    fall(i, n){
        for(int mc=fim+id; id<mc && id<m && v[id].f <= i+1; id++) cout << v[id].s << " ";
        
        cout << "0\n";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2280 KB Output is correct
2 Correct 43 ms 2236 KB Output is correct
3 Correct 43 ms 2228 KB Output is correct
4 Correct 44 ms 2236 KB Output is correct
5 Correct 49 ms 2304 KB Output is correct
6 Correct 44 ms 2188 KB Output is correct
7 Correct 54 ms 2212 KB Output is correct
8 Correct 44 ms 2232 KB Output is correct
9 Correct 70 ms 2496 KB Output is correct
10 Correct 73 ms 2460 KB Output is correct
11 Correct 57 ms 2352 KB Output is correct
12 Correct 125 ms 4516 KB Output is correct
13 Correct 204 ms 6524 KB Output is correct
14 Correct 285 ms 8892 KB Output is correct
15 Correct 369 ms 10596 KB Output is correct
16 Correct 444 ms 13612 KB Output is correct
17 Correct 504 ms 15720 KB Output is correct
18 Correct 563 ms 16936 KB Output is correct
19 Correct 645 ms 19168 KB Output is correct
20 Correct 514 ms 15592 KB Output is correct