oj.uz

Submission #1051929

# Submission time Handle Problem Language Result Execution time Memory
1051929 2024-08-10T10:40:18 Z manhlinh1501 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 157 ms 14160 KB 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int MAXN = 1e6 + 5;

int N, M, D;
int a[MAXN];
int idx[MAXN];

bool check(int K) {
    int j = 1;
    for(int i = 1; i <= N; i++) {
        if(i - D > a[idx[j]]) return false;
        int cnt = 0;
        while(j <= M and cnt < K and a[idx[j]] <= i) {
            j++;
            cnt++;
        }
        if(j > M) return true;
    }
    return j > M;
}

signed main() {
#define TASK "code"

    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }

    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];
    iota(idx + 1, idx + M + 1, 1);
    sort(idx + 1, idx + M + 1, [&](const int x, const int y) {
        return a[x] < a[y];
    });
    int low = 1, high = M;
    int ans = -1;
    while(low <= high) {
        int mid = (low + high) / 2;
        if(check(mid)) {
            ans = mid;
            high = mid - 1;
        } else low = mid + 1;
    }
    cout << ans << "\n";
    int j = 1;
    for(int i = 1; i <= N; i++) {
        if(j > M) {
            cout << 0 << "\n";
            continue;
        }
        int cnt = 0;
        while(j <= M and cnt < ans and a[idx[j]] <= i) {
            cout << idx[j] << " ";
            j++;
            cnt++;
        }
        cout << "0\n";
    }

    return (0 ^ 0);
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7256 KB Output is correct
2 Correct 10 ms 7256 KB Output is correct
3 Correct 9 ms 7380 KB Output is correct
4 Correct 10 ms 7260 KB Output is correct
5 Correct 10 ms 7260 KB Output is correct
6 Correct 9 ms 7308 KB Output is correct
7 Correct 9 ms 7380 KB Output is correct
8 Correct 10 ms 7260 KB Output is correct
9 Correct 15 ms 7516 KB Output is correct
10 Correct 15 ms 7548 KB Output is correct
11 Correct 13 ms 7348 KB Output is correct
12 Correct 28 ms 8020 KB Output is correct
13 Correct 47 ms 8532 KB Output is correct
14 Correct 64 ms 9296 KB Output is correct
15 Correct 71 ms 10068 KB Output is correct
16 Correct 95 ms 10884 KB Output is correct
17 Correct 117 ms 11860 KB Output is correct
18 Correct 118 ms 12880 KB Output is correct
19 Correct 157 ms 14160 KB Output is correct
20 Correct 111 ms 11760 KB Output is correct