oj.uz

Submission #858046

# Submission time Handle Problem Language Result Execution time Memory
858046 2023-10-07T11:07:17 Z AminMDNZ Job Scheduling (CEOI12_jobs) C++14
55 / 100
 379 ms 20260 KB 
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> arr;
int n, m, d;
vector<vector<int>> day;

bool f(int mm){
    int del = 0;
    day.clear();
    day.resize(n+1);
    queue<int> mac;
    for(int i=0;i<mm;i++) mac.push(1);
    for(int i=0;i<m;i++){
        int r = mac.front();
        del = max(r - arr[i].first, del);
        if(del > d) return false;
        day[max(r, arr[i].first)].push_back(arr[i].second);
        mac.pop();
        mac.push(r+1);
    }
    return true;
}
 
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 = m;
    while(r >= l){
        mm = l + (r - l)/2;
        if(f(mm)){
            r = mm - 1;
            ans = mm;
        }
        else{
            l = mm + 1;
        }
    }
    f(ans);
    cout<<ans<<endl;
    for(int i=1;i<n+1;i++){
        for(auto t : day[i]) cout<<t+1<<" ";
        cout<<"0\n";
    }
}

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 2816 KB Output isn't correct
2 Incorrect 31 ms 2960 KB Output isn't correct
3 Incorrect 31 ms 2964 KB Output isn't correct
4 Incorrect 31 ms 2912 KB Output isn't correct
5 Incorrect 31 ms 2948 KB Output isn't correct
6 Incorrect 33 ms 2952 KB Output isn't correct
7 Incorrect 30 ms 2964 KB Output isn't correct
8 Incorrect 31 ms 3020 KB Output isn't correct
9 Correct 43 ms 4924 KB Output is correct
10 Correct 42 ms 4772 KB Output is correct
11 Correct 42 ms 2464 KB Output is correct
12 Correct 83 ms 4112 KB Output is correct
13 Correct 121 ms 7036 KB Output is correct
14 Correct 190 ms 9016 KB Output is correct
15 Incorrect 209 ms 10284 KB Output isn't correct
16 Correct 274 ms 12812 KB Output is correct
17 Correct 350 ms 15996 KB Output is correct
18 Correct 349 ms 16312 KB Output is correct
19 Correct 379 ms 20260 KB Output is correct
20 Correct 338 ms 16020 KB Output is correct