oj.uz

Submission #854401

# Submission time Handle Problem Language Result Execution time Memory
854401 2023-09-27T09:47:50 Z anhphant Job Scheduling (CEOI12_jobs) C++14
100 / 100
 221 ms 21376 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
 
ll N, D, M;
pair<ll, ll> A[1000007];
 
void initialize() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N >> D >> M;
    for(int i = 1; i <= M; ++i) {
        cin >> A[i].first;
        A[i].second = i;
    }
    
    sort(A + 1, A + 1 + M);
}
 
bool check(ll MachinesCnt) {
    int idx = 1;
    
    for(int day = 1; day <= N; ++day) {
        ll used_machines_in_day = 0;
        while(idx <= M && used_machines_in_day < MachinesCnt) {
            if (A[idx].first + D < day) return 0;
            if (day < A[idx].first) break;
            
            used_machines_in_day++;
            idx++;
        }
    }
    
    return idx > M;
}
 
void construct(ll MachinesCnt) {
    int idx = 1;
    
    for(int day = 1; day <= N; ++day) {
        ll used_machines_in_day = 0;
        while(idx <= M && used_machines_in_day < MachinesCnt) {
            if (day < A[idx].first) break;
            
            cout << A[idx].second << " ";
            used_machines_in_day++;
            idx++;
        }
        
        cout << 0 << endl;    
    }
}
 
void process() {
    ll l = 1, r = 1e12;
    while(l < r) {
        ll mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    cout << l << endl;
    construct(l);
}
 
int main() {
    initialize();
    process();
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3160 KB Output is correct
2 Correct 16 ms 3192 KB Output is correct
3 Correct 20 ms 3240 KB Output is correct
4 Correct 16 ms 3200 KB Output is correct
5 Correct 16 ms 3160 KB Output is correct
6 Correct 16 ms 3160 KB Output is correct
7 Correct 16 ms 3164 KB Output is correct
8 Correct 16 ms 3164 KB Output is correct
9 Correct 30 ms 3420 KB Output is correct
10 Correct 31 ms 3420 KB Output is correct
11 Correct 23 ms 3164 KB Output is correct
12 Correct 46 ms 5980 KB Output is correct
13 Correct 72 ms 8564 KB Output is correct
14 Correct 119 ms 9388 KB Output is correct
15 Correct 118 ms 12148 KB Output is correct
16 Correct 145 ms 14976 KB Output is correct
17 Correct 170 ms 17536 KB Output is correct
18 Correct 189 ms 20564 KB Output is correct
19 Correct 221 ms 21376 KB Output is correct
20 Correct 173 ms 17748 KB Output is correct