oj.uz

답안 #441760

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
441760 2021-07-06T03:49:32 Z Yuisuyuno Job Scheduling (CEOI12_jobs) C++14
95 / 100
 330 ms 34756 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;
vector<ii> a;

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

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:48:23: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |     int l = 0, r = m, ans;
      |                       ^~~

Subtask #1
95.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 6088 KB Output is correct
2 Correct 27 ms 6160 KB Output is correct
3 Correct 29 ms 6048 KB Output is correct
4 Correct 27 ms 6088 KB Output is correct
5 Correct 27 ms 6032 KB Output is correct
6 Correct 27 ms 6032 KB Output is correct
7 Correct 27 ms 6032 KB Output is correct
8 Correct 27 ms 6028 KB Output is correct
9 Correct 37 ms 6308 KB Output is correct
10 Correct 38 ms 6340 KB Output is correct
11 Correct 34 ms 6152 KB Output is correct
12 Correct 70 ms 9884 KB Output is correct
13 Correct 103 ms 14532 KB Output is correct
14 Correct 143 ms 18256 KB Output is correct
15 Correct 178 ms 19844 KB Output is correct
16 Correct 217 ms 23620 KB Output is correct
17 Correct 255 ms 31044 KB Output is correct
18 Correct 286 ms 32048 KB Output is correct
19 Runtime error 330 ms 34756 KB Memory limit exceeded
20 Correct 254 ms 31148 KB Output is correct