Submission #441757

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
441757	2021-07-06T03:46:24 Z	Yuisuyuno	Job Scheduling (CEOI12_jobs)	C++14	95 / 100	320 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 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

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