oj.uz

Submission #856994

# Submission time Handle Problem Language Result Execution time Memory
856994 2023-10-05T07:29:45 Z AminMDNZ Job Scheduling (CEOI12_jobs) C++14
0 / 100
 1000 ms 49604 KB 
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> arr;
int n, m , d;
map<int, set<int>> day;
map<int, int> mac;
bool f(int mm){
    mac.clear();
    day.clear();
    int del = 0;
    mac[1] += mm;
    for(int i=0;i<m;i++){
        auto it = mac.lower_bound(-1);
        int r = (*it).first;
        // cout<<(*it).first<<endl;
        del = max(r - arr[i].first, d);
        day[r].insert(arr[i].second);
        mac[r + 1]++;
        if(mac[r] > 1) mac[r]--;
        else mac.erase(r);
    }
    return del <= d;
}

int main(){
    cin>>n>>d>>m;
    arr.resize(m);
    for(int i=0;i<m;i++){
        arr[i].second = i;
        cin>>arr[i].first;
    }
    sort(arr.begin(), arr.end());
    int mm;
    int r = m;
    int l = 1;
    int ans = -1;
    while(r >= l){
        mm = l + (r - l)/2;
        if(f(mm)){
            r = mm - 1;
            ans = mm;
        }
        else{
            l = mm + 1;
        }
    }
    f(ans);
    for(auto i : day){
        for(auto t : i.second) cout<<t+1<<" ";
        cout<<"0 \n";
    }
    cout<<"0 \n0";
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 175 ms 6684 KB Expected EOLN
2 Incorrect 174 ms 6484 KB Expected EOLN
3 Incorrect 167 ms 6596 KB Expected EOLN
4 Incorrect 166 ms 6484 KB Expected EOLN
5 Incorrect 167 ms 6480 KB Expected EOLN
6 Incorrect 167 ms 6484 KB Expected EOLN
7 Incorrect 158 ms 6480 KB Expected EOLN
8 Incorrect 156 ms 6484 KB Expected EOLN
9 Incorrect 194 ms 6736 KB Expected EOLN
10 Incorrect 209 ms 6484 KB Expected EOLN
11 Incorrect 226 ms 6436 KB Expected EOLN
12 Incorrect 546 ms 12664 KB Expected EOLN
13 Incorrect 917 ms 18916 KB Expected EOLN
14 Execution timed out 1031 ms 22596 KB Time limit exceeded
15 Execution timed out 1030 ms 27832 KB Time limit exceeded
16 Execution timed out 1077 ms 33300 KB Time limit exceeded
17 Execution timed out 1073 ms 38772 KB Time limit exceeded
18 Execution timed out 1047 ms 44112 KB Time limit exceeded
19 Execution timed out 1036 ms 49604 KB Time limit exceeded
20 Execution timed out 1073 ms 38800 KB Time limit exceeded