oj.uz

답안 #1057164

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1057164 2024-08-13T14:38:09 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 135 ms 17488 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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 7516 KB Output is correct
2 Correct 9 ms 7676 KB Output is correct
3 Correct 10 ms 7512 KB Output is correct
4 Correct 10 ms 7512 KB Output is correct
5 Correct 9 ms 7620 KB Output is correct
6 Correct 10 ms 7496 KB Output is correct
7 Correct 10 ms 7512 KB Output is correct
8 Correct 10 ms 7516 KB Output is correct
9 Correct 15 ms 7772 KB Output is correct
10 Correct 15 ms 7808 KB Output is correct
11 Correct 16 ms 7768 KB Output is correct
12 Correct 29 ms 8788 KB Output is correct
13 Correct 43 ms 9812 KB Output is correct
14 Correct 63 ms 11344 KB Output is correct
15 Correct 71 ms 11856 KB Output is correct
16 Correct 98 ms 13644 KB Output is correct
17 Correct 112 ms 15188 KB Output is correct
18 Correct 121 ms 15908 KB Output is correct
19 Correct 135 ms 17488 KB Output is correct
20 Correct 112 ms 15184 KB Output is correct