Submission #441761

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
441761	2021-07-06T03:50:28 Z	Yuisuyuno	Job Scheduling (CEOI12_jobs)	C++14	95 / 100	325 ms	34756 KB

jobs

//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+1] = {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:58:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |     int endT[ans+1] = {0};
      |         ^~~~

Subtask #1

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	6036 KB	Output is correct
2	Correct	27 ms	6096 KB	Output is correct
3	Correct	26 ms	6096 KB	Output is correct
4	Correct	27 ms	6036 KB	Output is correct
5	Correct	26 ms	6096 KB	Output is correct
6	Correct	26 ms	6044 KB	Output is correct
7	Correct	28 ms	6164 KB	Output is correct
8	Correct	27 ms	6032 KB	Output is correct
9	Correct	36 ms	6212 KB	Output is correct
10	Correct	37 ms	6344 KB	Output is correct
11	Correct	35 ms	6148 KB	Output is correct
12	Correct	69 ms	9800 KB	Output is correct
13	Correct	105 ms	14532 KB	Output is correct
14	Correct	142 ms	18372 KB	Output is correct
15	Correct	172 ms	19844 KB	Output is correct
16	Correct	213 ms	23588 KB	Output is correct
17	Correct	263 ms	31172 KB	Output is correct
18	Correct	283 ms	31964 KB	Output is correct
19	Runtime error	325 ms	34756 KB	Memory limit exceeded
20	Correct	252 ms	31152 KB	Output is correct