oj.uz

답안 #441758

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
441758 2021-07-06T03:47:13 Z Yuisuyuno Job Scheduling (CEOI12_jobs) C++14
95 / 100
 325 ms 34628 KB 
//Nguyen Huu Hoang Minh
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define reset(x) memset(x, 0,sizeof(x))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define N 1000001
#define remain(x) if (x > MOD) x -= MOD
#define ii pair<int, int>
#define iiii pair< ii , ii >
#define viiii vector< iiii >
#define vi vector<int>
#define vii vector< ii >
#define bit(x, i) (((x) >> (i)) & 1)
#define Task "test"
#define int long long

using namespace std;

typedef long double ld;
const int inf = 1e10;
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);
    /*
    8 2 12
    1 2 4 2 1 3 5 6 2 3 6 4
    */
    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:64:23: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     int l = 0, r = m, ans;
      |                       ^~~

Subtask #1
95.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 6096 KB Output is correct
2 Correct 27 ms 6032 KB Output is correct
3 Correct 29 ms 6120 KB Output is correct
4 Correct 27 ms 6108 KB Output is correct
5 Correct 26 ms 6108 KB Output is correct
6 Correct 27 ms 6044 KB Output is correct
7 Correct 27 ms 6024 KB Output is correct
8 Correct 27 ms 6028 KB Output is correct
9 Correct 38 ms 6268 KB Output is correct
10 Correct 40 ms 6340 KB Output is correct
11 Correct 38 ms 6212 KB Output is correct
12 Correct 68 ms 9856 KB Output is correct
13 Correct 105 ms 14492 KB Output is correct
14 Correct 146 ms 18260 KB Output is correct
15 Correct 172 ms 19776 KB Output is correct
16 Correct 215 ms 23708 KB Output is correct
17 Correct 253 ms 31296 KB Output is correct
18 Correct 295 ms 31868 KB Output is correct
19 Runtime error 325 ms 34628 KB Memory limit exceeded
20 Correct 255 ms 31156 KB Output is correct