Submission #456483

#	Time	Username	Problem	Language	Result	Execution time	Memory
456483		bill_lin	Job Scheduling (CEOI12_jobs)	C++14	40 / 100	615 ms	45468 KiB

jobs

#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 / 100