Submission #1004389

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1004389	2024-06-21T08:27:54 Z	u_suck_o	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	251 ms	10928 KB

jobs

#include <iostream>
#include <vector>
#include <queue>
#define MAXN 100005

using namespace std;

int n, d, m;
vector<int> tasks[MAXN];

int main() {
    cin >> n >> d >> m;
    for (int i = 1; i <= m; i++) {
        int x; cin >> x;
        tasks[x].push_back(i);
    }
    //binary search on answer
    int l = 1, r = m;
    while (l < r) {
        int mid = (l+r)/2;
        queue<pair<int, int>> q;
        bool valid = true;
        for (int i = 1; i <= n; i++) {
            for (int j : tasks[i])
                q.push({j, i});
            for (int j = 1; j <= mid; j++) {
                if (!q.empty()) {
                    auto p = q.front(); q.pop();
                    if (i - p.second > d) {
                        valid = false;
                        break;
                    }
                } else
                    break;
            }
            if (!valid)
                break;
        }
        if (!q.empty())
            valid = false;
        if (valid)
            r = mid;
        else
            l = mid+1;
    }
    
    cout << r << "\n";
    //make assignments
    queue<pair<int, int>> q;
    //vector<int> v[n];
    for (int i = 1; i <= n; i++) {
        for (int j : tasks[i])
            q.push({j, i});
        for (int j = 1; j <= r; j++) {
            if (!q.empty()) {
                //v[i].push_back(q.front().first);
                q.pop();
            }
            else
                break;
        }
    }
    for (int i = 1; i <= n; i++) {
        //for (int j : v[i])
            //cout << j << " ";
        cout << "0\n";
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	4260 KB	Output is correct
2	Correct	26 ms	4348 KB	Output is correct
3	Correct	25 ms	4308 KB	Output is correct
4	Correct	29 ms	4284 KB	Output is correct
5	Correct	26 ms	4260 KB	Output is correct
6	Correct	26 ms	4340 KB	Output is correct
7	Correct	35 ms	4340 KB	Output is correct
8	Correct	27 ms	4304 KB	Output is correct
9	Correct	27 ms	3692 KB	Output is correct
10	Correct	28 ms	3676 KB	Output is correct
11	Correct	26 ms	3764 KB	Output is correct
12	Correct	51 ms	4644 KB	Output is correct
13	Correct	75 ms	5956 KB	Output is correct
14	Correct	116 ms	7468 KB	Output is correct
15	Correct	124 ms	7612 KB	Output is correct
16	Correct	163 ms	9132 KB	Output is correct
17	Correct	201 ms	10828 KB	Output is correct
18	Correct	207 ms	9556 KB	Output is correct
19	Correct	251 ms	10324 KB	Output is correct
20	Correct	196 ms	10928 KB	Output is correct