oj.uz

답안 #392779

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
392779 2021-04-21T16:24:58 Z nicolaalexandra Job Scheduling (CEOI12_jobs) C++14
65 / 100
 1000 ms 41060 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){
    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

# 결과 실행 시간 메모리 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