Submission #392779

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
392779	2021-04-21T16:24:58 Z	nicolaalexandra	Job Scheduling (CEOI12_jobs)	C++14	65 / 100	1000 ms	41060 KB

jobs

#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){
    while (!h.empty())
        h.pop();
    for (int i=1;i<=m;i++)
        ans[i].clear();

    for (int i=1;i<=val;i++)
        h.push(1);

    for (int i=1;i<=n;i++){
        int day = h.top();
        h.pop();
        if (day > v[i].first + d)
            return 0;

        ans[max(day,v[i].first)].push_back(v[i].second);
        h.push(max(day+1,v[i].first+1));
    }

    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:54:16: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     cout<<sol<<"\n";
      |                ^~~~

Subtask #1

65.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	25948 KB	Output is correct
2	Correct	180 ms	25912 KB	Output is correct
3	Correct	180 ms	25928 KB	Output is correct
4	Correct	173 ms	25908 KB	Output is correct
5	Correct	172 ms	25928 KB	Output is correct
6	Correct	175 ms	26000 KB	Output is correct
7	Correct	174 ms	25908 KB	Output is correct
8	Correct	174 ms	25904 KB	Output is correct
9	Correct	159 ms	26096 KB	Output is correct
10	Correct	155 ms	26276 KB	Output is correct
11	Correct	134 ms	25920 KB	Output is correct
12	Correct	276 ms	28120 KB	Output is correct
13	Correct	415 ms	30772 KB	Output is correct
14	Runtime error	570 ms	33236 KB	Memory limit exceeded
15	Runtime error	691 ms	35092 KB	Memory limit exceeded
16	Runtime error	879 ms	37360 KB	Memory limit exceeded
17	Execution timed out	1033 ms	41060 KB	Time limit exceeded
18	Execution timed out	1094 ms	35772 KB	Time limit exceeded
19	Execution timed out	1092 ms	36656 KB	Time limit exceeded
20	Execution timed out	1006 ms	41016 KB	Time limit exceeded