oj.uz

Submission #392795

# Submission time Handle Problem Language Result Execution time Memory
392795 2021-04-21T17:10:54 Z nicolaalexandra Job Scheduling (CEOI12_jobs) C++14
100 / 100
 506 ms 20124 KB 
#include <bits/stdc++.h>
#define DIM 1000010
#define DIMN 100010
using namespace std;

pair <int,int> v[DIM];
vector <int> ans[DIMN];
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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 4456 KB Output is correct
2 Correct 44 ms 4468 KB Output is correct
3 Correct 43 ms 4548 KB Output is correct
4 Correct 43 ms 4552 KB Output is correct
5 Correct 45 ms 4552 KB Output is correct
6 Correct 44 ms 4568 KB Output is correct
7 Correct 43 ms 4480 KB Output is correct
8 Correct 44 ms 4440 KB Output is correct
9 Correct 57 ms 4704 KB Output is correct
10 Correct 57 ms 4700 KB Output is correct
11 Correct 63 ms 4420 KB Output is correct
12 Correct 111 ms 6512 KB Output is correct
13 Correct 162 ms 8944 KB Output is correct
14 Correct 255 ms 11204 KB Output is correct
15 Correct 273 ms 12844 KB Output is correct
16 Correct 352 ms 14928 KB Output is correct
17 Correct 409 ms 18756 KB Output is correct
18 Correct 460 ms 18492 KB Output is correct
19 Correct 506 ms 20124 KB Output is correct
20 Correct 458 ms 18368 KB Output is correct