Submission #1057164

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1057164	2024-08-13T14:38:09 Z	vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	135 ms	17488 KB

jobs

#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	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