oj.uz

답안 #540454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
540454 2022-03-20T11:22:33 Z BhavayGoyal Job Scheduling (CEOI12_jobs) C++14
100 / 100
 503 ms 26452 KB 
#include <bits/stdc++.h>
using namespace std;

#define vii vector<vector<int>>
#define pii pair<int, int>
#define f first
#define s second
int inf = 1e9;

int n, d, m; 

pair<bool, vii> isFiss(int mid, vector<pii> &arr)
{
    int idx = 0;
    vii answer(n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < mid; j++)
        {
            if (arr[idx].f > i) break;
            if (i <= arr[idx].f + d) answer[i-1].push_back(arr[idx++].s);
            else return {false, answer};
            if (idx == m) return {true, answer};
        }
    }
    return {false, answer};
}

void sol()
{
    cin >> n >> d >> m;
    vector<pii> arr(m);
    for (int i = 0; i < m; i++)
    {
        cin >> arr[i].f;
        arr[i].s = i+1;
    }
    sort (arr.begin(), arr.end());

    int i = 1, j = m;
    int ans = m;
    vii actualans;
    while (i <= j)
    {
        int mid = (i+j)/2;
        auto f = isFiss(mid, arr);
        if (f.f)
        {
            actualans = f.s;
            ans = mid;
            j = mid-1;
        }
        else i = mid+1;
    }
    cout << ans << endl;
    for (int i = 0; i < n; i++)
    {
        for (auto j : actualans[i]) cout << j << " ";
        cout << 0 << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
        sol();
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 2968 KB Output is correct
2 Correct 41 ms 3004 KB Output is correct
3 Correct 41 ms 3000 KB Output is correct
4 Correct 42 ms 3084 KB Output is correct
5 Correct 41 ms 2968 KB Output is correct
6 Correct 44 ms 3020 KB Output is correct
7 Correct 49 ms 2976 KB Output is correct
8 Correct 41 ms 3076 KB Output is correct
9 Correct 189 ms 9672 KB Output is correct
10 Correct 184 ms 9708 KB Output is correct
11 Correct 39 ms 2752 KB Output is correct
12 Correct 78 ms 4984 KB Output is correct
13 Correct 108 ms 8576 KB Output is correct
14 Correct 190 ms 10792 KB Output is correct
15 Correct 188 ms 10920 KB Output is correct
16 Correct 271 ms 15760 KB Output is correct
17 Correct 345 ms 18844 KB Output is correct
18 Correct 358 ms 18256 KB Output is correct
19 Correct 503 ms 26452 KB Output is correct
20 Correct 323 ms 18900 KB Output is correct