Submission #441758

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
441758	2021-07-06T03:47:13 Z	Yuisuyuno	Job Scheduling (CEOI12_jobs)	C++14	95 / 100	325 ms	34628 KB

jobs

//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

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