oj.uz

Submission #1051926

# Submission time Handle Problem Language Result Execution time Memory
1051926 2024-08-10T10:37:54 Z manhlinh1501 Job Scheduling (CEOI12_jobs) C++17
40 / 100
 138 ms 13396 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++) {
        int cnt = 0;
        while(j <= M and cnt < ans and a[idx[j]] <= i) {
            cout << a[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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 7512 KB Partially correct
2 Partially correct 9 ms 7256 KB Partially correct
3 Partially correct 9 ms 7260 KB Partially correct
4 Partially correct 12 ms 7168 KB Partially correct
5 Partially correct 9 ms 7260 KB Partially correct
6 Partially correct 10 ms 7512 KB Partially correct
7 Partially correct 9 ms 7256 KB Partially correct
8 Partially correct 17 ms 7188 KB Partially correct
9 Partially correct 12 ms 7376 KB Partially correct
10 Partially correct 14 ms 7256 KB Partially correct
11 Partially correct 16 ms 7432 KB Partially correct
12 Partially correct 40 ms 7912 KB Partially correct
13 Partially correct 43 ms 8532 KB Partially correct
14 Partially correct 87 ms 9844 KB Partially correct
15 Partially correct 74 ms 9848 KB Partially correct
16 Partially correct 96 ms 11432 KB Partially correct
17 Partially correct 113 ms 12372 KB Partially correct
18 Partially correct 129 ms 12368 KB Partially correct
19 Partially correct 138 ms 13396 KB Partially correct
20 Partially correct 126 ms 12372 KB Partially correct