oj.uz

Submission #1051860

# Submission time Handle Problem Language Result Execution time Memory
1051860 2024-08-10T10:15:57 Z manhlinh1501 Job Scheduling (CEOI12_jobs) C++17
65 / 100
 133 ms 38228 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];
vector<int> g[MAXN];

bool check(int K) {
    queue<int> Q;
    for(int i = 0; i <= N; i++) {
        for(int p : g[i])
            Q.emplace(p);
        int cnt = 0;
        while(!Q.empty() and cnt < K) {
            int p = Q.front();
            if(i - D > a[p])
                return false;
            Q.pop();
            cnt++;
        }
    }
    return Q.empty();
}

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];
    }
    for(int i = 1; i <= M; i++) g[a[i]].emplace_back(i);
    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";
    queue<int> Q;
    for(int i = 1; i <= N; i++) {
        for(int p : g[i])
            Q.emplace(p);
        int cnt = 0;
        while(!Q.empty() and cnt < ans) {
            int p = Q.front();
            cout << p << " ";
            Q.pop();
            cnt++;
        }
        cout << "0\n";
    }
    return (0 ^ 0);
}

Compilation message

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

Subtask #1
65.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26588 KB Output is correct
2 Correct 17 ms 26584 KB Output is correct
3 Correct 17 ms 26588 KB Output is correct
4 Correct 17 ms 26588 KB Output is correct
5 Correct 24 ms 26588 KB Output is correct
6 Correct 16 ms 26588 KB Output is correct
7 Correct 14 ms 26628 KB Output is correct
8 Correct 14 ms 26588 KB Output is correct
9 Correct 17 ms 26540 KB Output is correct
10 Correct 17 ms 26460 KB Output is correct
11 Correct 16 ms 26200 KB Output is correct
12 Correct 28 ms 27476 KB Output is correct
13 Correct 42 ms 29348 KB Output is correct
14 Runtime error 58 ms 32848 KB Memory limit exceeded
15 Runtime error 65 ms 33580 KB Memory limit exceeded
16 Runtime error 105 ms 35236 KB Memory limit exceeded
17 Runtime error 127 ms 37200 KB Memory limit exceeded
18 Runtime error 106 ms 37060 KB Memory limit exceeded
19 Runtime error 133 ms 38228 KB Memory limit exceeded
20 Runtime error 104 ms 37200 KB Memory limit exceeded