oj.uz

Submission #392794

# Submission time Handle Problem Language Result Execution time Memory
392794 2021-04-21T17:09:57 Z nicolaalexandra Job Scheduling (CEOI12_jobs) C++14
70 / 100
 513 ms 41212 KB 
#include <bits/stdc++.h>
#define DIM 1000010
using namespace std;

priority_queue <int,vector<int>,greater<int> > h;
pair <int,int> v[DIM];
vector <int> ans[DIM];
int n,d,m,i;

int verif (int val){

    for (int i=1;i<=m;i++)
        ans[i].clear();

    int pos = 1;
    for (int i=1;i<=m;i++){
        /// ce fac in ziua i?
        int cnt = 0;
        while (pos <= n && v[pos].first <= i && cnt < val){

            if (v[pos].first + d < i)
                return 0;

            ans[i].push_back(v[pos].second);
            cnt++;

            pos++;
        }
    }

    return 1;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>m>>d>>n;
    for (i=1;i<=n;i++){
        cin>>v[i].first;
        v[i].second = i;
    }

    sort (v+1,v+n+1);

    int st = 1, dr = n, sol;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif(mid)){
            sol = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    cout<<sol<<"\n";
    verif (sol);

    for (i=1;i<=m;i++){
        for (auto it : ans[i])
            cout<<it<<" ";
        cout<<"0\n";
    }



    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:56:16: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |     cout<<sol<<"\n";
      |                ^~~~

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 25612 KB Output is correct
2 Correct 57 ms 25624 KB Output is correct
3 Correct 56 ms 25684 KB Output is correct
4 Correct 55 ms 25668 KB Output is correct
5 Correct 56 ms 25668 KB Output is correct
6 Correct 63 ms 25664 KB Output is correct
7 Correct 58 ms 25668 KB Output is correct
8 Correct 55 ms 25676 KB Output is correct
9 Correct 70 ms 25828 KB Output is correct
10 Correct 73 ms 25924 KB Output is correct
11 Correct 69 ms 25592 KB Output is correct
12 Correct 124 ms 27640 KB Output is correct
13 Correct 173 ms 30080 KB Output is correct
14 Correct 244 ms 32220 KB Output is correct
15 Runtime error 279 ms 34000 KB Memory limit exceeded
16 Runtime error 357 ms 35916 KB Memory limit exceeded
17 Runtime error 450 ms 39540 KB Memory limit exceeded
18 Runtime error 453 ms 39620 KB Memory limit exceeded
19 Runtime error 513 ms 41212 KB Memory limit exceeded
20 Runtime error 437 ms 39620 KB Memory limit exceeded