oj.uz

답안 #441757

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
441757 2021-07-06T03:46:24 Z Yuisuyuno Job Scheduling (CEOI12_jobs) C++14
95 / 100
 320 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 1000005
#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 6140 KB Output is correct
2 Correct 27 ms 6112 KB Output is correct
3 Correct 26 ms 6160 KB Output is correct
4 Correct 26 ms 6168 KB Output is correct
5 Correct 26 ms 6088 KB Output is correct
6 Correct 27 ms 6224 KB Output is correct
7 Correct 27 ms 6176 KB Output is correct
8 Correct 27 ms 6148 KB Output is correct
9 Correct 37 ms 6244 KB Output is correct
10 Correct 37 ms 6212 KB Output is correct
11 Correct 34 ms 6144 KB Output is correct
12 Correct 69 ms 9848 KB Output is correct
13 Correct 104 ms 14576 KB Output is correct
14 Correct 142 ms 18324 KB Output is correct
15 Correct 173 ms 19824 KB Output is correct
16 Correct 216 ms 23632 KB Output is correct
17 Correct 252 ms 31184 KB Output is correct
18 Correct 282 ms 31992 KB Output is correct
19 Runtime error 320 ms 34628 KB Memory limit exceeded
20 Correct 250 ms 31236 KB Output is correct