제출 #1193954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193954		Hamed_Ghaffari	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	155 ms	20316 KiB

jobs

#include<bits/stdc++.h>
using namespace std;

const int MXN = 1e5+5;

int n, m, d;
vector<int> vec[MXN], ans[MXN];

bool check(int mid) {
    queue<pair<int, int>> q;
    for(int i=1; i<=n; i++) {
        for(int j : vec[i])
            q.push({j, i});
        if(!q.empty() && q.front().second+d<i) return 0;
        ans[i].clear();
        for(int j=0; j<mid && !q.empty(); j++) {
            ans[i].push_back(q.front().first);
            q.pop();
        }
    }
    return q.empty();
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> d >> m;
    for(int i=1; i<=m; i++) {
        int x;
        cin >> x;
        vec[x].push_back(i);
    }
    int l=0, r=m;
    while(r-l>1) {
        int mid = ((l+r)>>1);
        (check(mid) ? r : l) = mid;
    }
    check(r);
    cout << r << '\n';
    for(int i=1; i<=n; i++) {
        for(int j : ans[i]) cout << j << ' ';
        cout << "0\n";
    }
}

• Subtask 1: 100 / 100