oj.uz

답안 #441759

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
441759 2021-07-06T03:48:26 Z Yuisuyuno Job Scheduling (CEOI12_jobs) C++14
95 / 100
 352 ms 34736 KB 
//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define N 1000001
#define ii pair<int, int>
#define vi vector<int>
#define int long long

using namespace std;
const int minf = -1e10;

int n, m, d;
ii a[N];

void readfile()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> d >> m;
    for(int i=1; i<=m; i++){
        cin >> a[i].fi;
        a[i].se = i;
    }
    sort(a+1,a+1+m);
}

bool ok(int machine){
    int endT[machine] = {0};
    int delays = minf;
    for(int i=1, cur=0; i<=m; i++, cur++){
        if (cur==machine) cur=0;
        if (endT[cur]+1 > a[i].first){
            endT[cur]++;
            delays = max(delays,endT[cur]-a[i].fi);
        }
        else endT[cur]=a[i].fi;
    }
    return delays <= d;
}

vector<int> res[100012];

void proc()
{
    int l = 0, r = m, ans;
    while (r >= l){
        int mid = (l+r)/2;
        if (ok(mid)){
            r = mid-1;
            ans=mid;
        }
        else l = mid+1;
    }
    cout << ans << '\n';
    int endT[ans] = {0};
    for(int i=1, cur=0; i<=m; i++, cur++){
        if (cur==ans) cur=0;
        endT[cur]=max(a[i].fi,endT[cur]+1);
        res[endT[cur]].pb(a[i].se);
    }
    for(int i=1; i<=n; i++){
        for(int x : res[i]) cout << x << ' ';
        cout << "0\n";
    }
}

signed main()
{
    readfile();
    proc();
    return 0;
}

Compilation message

jobs.cpp: In function 'void proc()':
jobs.cpp:47:23: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     int l = 0, r = m, ans;
      |                       ^~~

Subtask #1
95.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 6088 KB Output is correct
2 Correct 26 ms 6144 KB Output is correct
3 Correct 27 ms 6096 KB Output is correct
4 Correct 26 ms 6096 KB Output is correct
5 Correct 26 ms 6096 KB Output is correct
6 Correct 26 ms 6144 KB Output is correct
7 Correct 33 ms 6136 KB Output is correct
8 Correct 27 ms 6156 KB Output is correct
9 Correct 37 ms 6212 KB Output is correct
10 Correct 39 ms 6344 KB Output is correct
11 Correct 36 ms 6096 KB Output is correct
12 Correct 68 ms 9796 KB Output is correct
13 Correct 104 ms 14532 KB Output is correct
14 Correct 147 ms 18388 KB Output is correct
15 Correct 173 ms 19820 KB Output is correct
16 Correct 215 ms 23620 KB Output is correct
17 Correct 257 ms 31104 KB Output is correct
18 Correct 287 ms 32004 KB Output is correct
19 Runtime error 352 ms 34736 KB Memory limit exceeded
20 Correct 258 ms 31052 KB Output is correct