oj.uz

Submission #1000164

# Submission time Handle Problem Language Result Execution time Memory
1000164 2024-06-16T18:30:25 Z codexistent Job Scheduling (CEOI12_jobs) C++14
100 / 100
 340 ms 14160 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define MAXN 100005
#define MAXM 1000000

int n, d, m, arr[MAXN];
pair<int, int> req[MAXM];

int main(){
    cin >> n >> d >> m;
    FOR(i, 1, n) arr[i] = 0;
    FOR(i, 1, m){
        int x; cin >> x;
        arr[x]++;
        req[i - 1] = {x, i};
    }
    sort(req,  req + m);
// 4762
    multiset<int> s; 
    FOR(i, 1, 1 + d) s.insert(0);

    int a = 1, b = m;
    while(a < b){
        int mid = (a + b) / 2;
        bool valid = true;

        int k = -1;
        FOR(i, 1, n){
            int j = 1;
            while(j <= mid && (k + 1 < m) && (req[k + 1].first <= i && i <= req[k + 1].first + d)){
                j++, k++;
            }
            //cout << k + 1 << " " << req[k + 1].first << " ~ " << i << endl;
        }
        if(k != m - 1) valid = false;

        //cout << " YOYO m " << a << " is " << valid << " and we see " << k << endl;

        if(valid){
            b = mid;
        }else{
            a = mid + 1;
        }

    }

    cout << a << endl;

    int k = -1;
    FOR(i, 1, n){
        int j = 1;
        while(j <= a && (k + 1 < m) && (req[k + 1].first <= i && i <= req[k + 1].first + d)){
            cout << req[k + 1].second << " ";
            j++, k++;
        }

        cout << "0" << endl;
    }
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4

2 0 8
2 2 2 2 1 2 2 2
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1628 KB Output is correct
2 Correct 28 ms 1720 KB Output is correct
3 Correct 42 ms 1628 KB Output is correct
4 Correct 29 ms 1688 KB Output is correct
5 Correct 29 ms 1776 KB Output is correct
6 Correct 28 ms 1624 KB Output is correct
7 Correct 29 ms 1628 KB Output is correct
8 Correct 29 ms 1624 KB Output is correct
9 Correct 132 ms 2248 KB Output is correct
10 Correct 120 ms 2272 KB Output is correct
11 Correct 29 ms 1616 KB Output is correct
12 Correct 58 ms 3928 KB Output is correct
13 Correct 80 ms 6484 KB Output is correct
14 Correct 170 ms 7504 KB Output is correct
15 Correct 187 ms 8036 KB Output is correct
16 Correct 190 ms 10832 KB Output is correct
17 Correct 212 ms 11600 KB Output is correct
18 Correct 227 ms 12116 KB Output is correct
19 Correct 340 ms 14160 KB Output is correct
20 Correct 219 ms 11388 KB Output is correct