Submission #623539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
623539	2022-08-05T19:17:51 Z	binisgiannis	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	274 ms	13744 KB

jobs

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> pi;
#define x first 
#define y second 

int N, D, M; vector<pi> vec;

bool f(int &x) {
    int index = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < x; j++) {
            if (vec[index].x > (i+1)) break;
            if ((i+1) - vec[index].x > D) return false;
            index++;
            if (index >= M) goto endofloop;
        }
    }

    endofloop:
    return index >= M;
}

void res(int &x) {
    int index = 0, counter = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < x; j++) {
            if (index < M) {
                cout << vec[index].y << ' ';
                index++; 
            }
        }
        cout << 0 << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N >> D >> M;
    vec.resize(M);

    for (int i = 0; i < M; i++) {
        cin >> vec[i].x;
        vec[i].y = i+1;
    }

    sort(vec.begin(), vec.end());

    int l = 1, r = M, mid; 
    while (l < r) {
        mid = (l+r)/2;
        if (!f(mid)) l = mid+1;
        else {
            r = mid;
        }
    }

    cout << l << '\n';
    res(l);

    return 0;
}

Compilation message

jobs.cpp: In function 'void res(int&)':
jobs.cpp:29:20: warning: unused variable 'counter' [-Wunused-variable]
   29 |     int index = 0, counter = 0;
      |                    ^~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	180 ms	1704 KB	Output is correct
2	Correct	181 ms	1712 KB	Output is correct
3	Correct	184 ms	1620 KB	Output is correct
4	Correct	188 ms	1704 KB	Output is correct
5	Correct	201 ms	1620 KB	Output is correct
6	Correct	187 ms	1704 KB	Output is correct
7	Correct	186 ms	1768 KB	Output is correct
8	Correct	179 ms	1700 KB	Output is correct
9	Correct	191 ms	1920 KB	Output is correct
10	Correct	188 ms	1872 KB	Output is correct
11	Correct	24 ms	1628 KB	Output is correct
12	Correct	50 ms	3176 KB	Output is correct
13	Correct	75 ms	4580 KB	Output is correct
14	Correct	105 ms	6132 KB	Output is correct
15	Correct	124 ms	7556 KB	Output is correct
16	Correct	152 ms	9036 KB	Output is correct
17	Correct	179 ms	10540 KB	Output is correct
18	Correct	209 ms	12088 KB	Output is correct
19	Correct	274 ms	13744 KB	Output is correct
20	Correct	190 ms	10572 KB	Output is correct