oj.uz

Submission #456483

# Submission time Handle Problem Language Result Execution time Memory
456483 2021-08-06T22:40:51 Z bill_lin Job Scheduling (CEOI12_jobs) C++14
40 / 100
 615 ms 45468 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;
 
#define MOD 1000000007
#define INF 10000000
int n, d, m;
vector<pii> times;
vector<vector<int>> answer;

bool check(int mp) {
    queue<pii> tasks;
    vector<vector<int>> order(n);
    
    int ptr = 0;
    for (int i = 0; i < n; i++) {
        int curr_time = i + 1;
        while (ptr < m && times[ptr].first <= curr_time) {
            tasks.push(times[ptr++]);
        }
        
        for (int j = 0; j < mp; j++) {
            if (tasks.empty()) break;
            pii p = tasks.front();
            tasks.pop();
            if (p.first - curr_time > d) return false;
            order[i].push_back(p.second);
        }
    }
    
    if (!tasks.empty()) return false;
    answer = order;
    return true;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
//     freopen("angry.in", "r", stdin);
//     freopen("angry.out", "w", stdout);
    
    cin >> n >> d >> m;
    times.resize(m);
    for (int i = 0; i < m; i++) {
        ll x;
        cin >> x;
        times[i] = {x, i};
    }
    sort(times.begin(), times.end());
    
    int l = 0, r = m;
    int ans = 0;
    while (l <= r) {
        int mp = (l + r) / 2;
        if (check(mp)) {
            ans = mp;
            r = mp - 1;
        } else l = mp + 1;
    }
    cout << ans << '\n';
    for (int i = 0; i < n; i++) {
        for (int j : answer[i]) cout << j + 1 << ' ';
        cout << "0\n";
    }

}

/*
 8 2 12
 1 2 4 2 1 3 5 6 2 3 6 4
 */

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 6324 KB Output isn't correct
2 Incorrect 55 ms 6304 KB Output isn't correct
3 Incorrect 51 ms 6228 KB Output isn't correct
4 Incorrect 51 ms 6336 KB Output isn't correct
5 Incorrect 50 ms 6208 KB Output isn't correct
6 Incorrect 53 ms 6260 KB Output isn't correct
7 Incorrect 50 ms 6244 KB Output isn't correct
8 Incorrect 51 ms 6320 KB Output isn't correct
9 Incorrect 99 ms 15104 KB Output isn't correct
10 Incorrect 93 ms 15124 KB Output isn't correct
11 Correct 49 ms 3096 KB Output is correct
12 Correct 99 ms 5852 KB Output is correct
13 Correct 153 ms 8668 KB Output is correct
14 Correct 235 ms 12500 KB Output is correct
15 Correct 247 ms 13256 KB Output is correct
16 Correct 365 ms 16732 KB Output is correct
17 Correct 410 ms 20608 KB Output is correct
18 Incorrect 469 ms 29360 KB Output isn't correct
19 Runtime error 615 ms 45468 KB Memory limit exceeded
20 Correct 446 ms 20600 KB Output is correct