oj.uz

Submission #330608

# Submission time Handle Problem Language Result Execution time Memory
330608 2020-11-25T23:56:09 Z ewang Job Scheduling (CEOI12_jobs) C++14
55 / 100
 791 ms 25684 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXM 1000000
#define MAXN 100000
#define pb push_back
#define mp make_pair
#define f first
#define s second

int N, D, M;
pair<int, int> r[MAXM];
vector<int> ans[MAXN];

bool ok(int mid, bool last) {
    int prev[mid]; memset(prev, 0, sizeof prev);
    int day = -1;
    for (int i = 0; i < M; i++) {
        prev[i%mid]++;
        if (prev[i%mid]-r[i].f > D) {
            return 0;
        }

        if (last) {
            if (i%mid == 0) {
                day++;
            }
            ans[day].pb(r[i].s);
        }
    }
    return 1;
}

int main() {
    cin >> N >> D >> M;

    for (int i = 0; i < M; i++) {
        cin >> r[i].f;
        r[i].s = i+1;
    }
    sort(r, r+M);

    int a = 1, b = M;
    while (a != b) {
        int mid = (a+b)/2;
        if (ok(mid, false)) {
            b = mid;
        } else {
            a = mid+1;
        }
    }
    ok(a, true);
    
    cout << a << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < ans[i].size(); j++) {
            cout << ans[i][j] << " ";
        }
        cout << 0 << endl;
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int j = 0; j < ans[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 5100 KB Output isn't correct
2 Incorrect 67 ms 5100 KB Output isn't correct
3 Incorrect 69 ms 5100 KB Output isn't correct
4 Incorrect 68 ms 5228 KB Output isn't correct
5 Incorrect 69 ms 4972 KB Output isn't correct
6 Incorrect 69 ms 5228 KB Output isn't correct
7 Incorrect 68 ms 5100 KB Output isn't correct
8 Incorrect 68 ms 5228 KB Output isn't correct
9 Correct 273 ms 5356 KB Output is correct
10 Correct 272 ms 5228 KB Output is correct
11 Correct 61 ms 5100 KB Output is correct
12 Correct 120 ms 7808 KB Output is correct
13 Correct 179 ms 10860 KB Output is correct
14 Correct 273 ms 13932 KB Output is correct
15 Incorrect 295 ms 14988 KB Output isn't correct
16 Correct 395 ms 18156 KB Output is correct
17 Correct 468 ms 22764 KB Output is correct
18 Correct 502 ms 23136 KB Output is correct
19 Correct 791 ms 25684 KB Output is correct
20 Correct 457 ms 22764 KB Output is correct