Submission #441760

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
441760	2021-07-06T03:49:32 Z	Yuisuyuno	Job Scheduling (CEOI12_jobs)	C++14	95 / 100	330 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] = {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

#	Verdict	Execution time	Memory	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