oj.uz

Submission #858031

# Submission time Handle Problem Language Result Execution time Memory
858031 2023-10-07T10:41:01 Z AminMDNZ Job Scheduling (CEOI12_jobs) C++17
55 / 100
 455 ms 22848 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[r].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 = -1;
    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 40 ms 2884 KB Output isn't correct
2 Incorrect 42 ms 2820 KB Output isn't correct
3 Incorrect 34 ms 2836 KB Output isn't correct
4 Incorrect 36 ms 2928 KB Output isn't correct
5 Incorrect 38 ms 2700 KB Output isn't correct
6 Incorrect 35 ms 2944 KB Output isn't correct
7 Incorrect 33 ms 2944 KB Output isn't correct
8 Incorrect 34 ms 2904 KB Output isn't correct
9 Correct 45 ms 5160 KB Output is correct
10 Correct 45 ms 5256 KB Output is correct
11 Correct 43 ms 2928 KB Output is correct
12 Correct 98 ms 5220 KB Output is correct
13 Correct 137 ms 7884 KB Output is correct
14 Correct 189 ms 10708 KB Output is correct
15 Incorrect 212 ms 11280 KB Output isn't correct
16 Correct 294 ms 16340 KB Output is correct
17 Correct 337 ms 18704 KB Output is correct
18 Correct 364 ms 20248 KB Output is correct
19 Correct 455 ms 22848 KB Output is correct
20 Correct 348 ms 18680 KB Output is correct