oj.uz

Submission #1004378

# Submission time Handle Problem Language Result Execution time Memory
1004378 2024-06-21T08:23:39 Z u_suck_o Job Scheduling (CEOI12_jobs) C++17
0 / 100
 333 ms 37012 KB 
#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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 10056 KB Execution killed with signal 11
2 Runtime error 32 ms 10080 KB Execution killed with signal 11
3 Runtime error 32 ms 9980 KB Execution killed with signal 11
4 Runtime error 34 ms 9920 KB Execution killed with signal 11
5 Runtime error 32 ms 10056 KB Execution killed with signal 11
6 Runtime error 34 ms 9960 KB Execution killed with signal 11
7 Runtime error 31 ms 10060 KB Execution killed with signal 11
8 Runtime error 33 ms 10068 KB Execution killed with signal 11
9 Runtime error 34 ms 13508 KB Execution killed with signal 11
10 Runtime error 36 ms 13392 KB Execution killed with signal 11
11 Runtime error 32 ms 8476 KB Execution killed with signal 11
12 Runtime error 51 ms 10480 KB Execution killed with signal 6
13 Runtime error 89 ms 16980 KB Execution killed with signal 11
14 Runtime error 141 ms 18744 KB Execution killed with signal 6
15 Runtime error 127 ms 16976 KB Execution killed with signal 6
16 Runtime error 182 ms 25300 KB Execution killed with signal 11
17 Runtime error 230 ms 34376 KB Execution killed with signal 11
18 Runtime error 251 ms 31636 KB Execution killed with signal 11
19 Runtime error 333 ms 37012 KB Execution killed with signal 11
20 Runtime error 231 ms 34384 KB Execution killed with signal 11