oj.uz

Submission #742965

# Submission time Handle Problem Language Result Execution time Memory
742965 2023-05-17T07:03:05 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 61 ms 37256 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long ;
using pii = pair<ll , ll> ;
using i3 = tuple<ll , ll , ll> ;

const int N = 1e5+5 ;
const int MOD = 1e9+7 ;

ll n , d , m ;
pii S[N] ;

vector<ll> ans2[N] ;

bool solve(ll mid){

    ll day = 1 , cnt = 0 ;
    for(int i=1;i<=m;i++){
        if(day <= S[i].first + d){ // do job i
            cnt++ ;
            ans2[day].push_back(S[i].second) ;
        }
        else {
            return false ;
        }
        if(cnt == mid){
            day++;
            cnt = 0 ;
        }
    }

    if(cnt == 0) day--;

    return day <= n ;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> d >> m ;
    for(int i=1, x;i<=m;i++){
        cin >> x ;
        S[i] = {x , i};
    }

    sort(S+1 , S+m+1) ;

    ll l = 1 , r = 1e12 , ans ;

    while(l <= r){
        ll mid = (l+r)/2 ;

        if(solve(mid)){
            r = mid-1 ;
            ans = mid ;
        }
        else {
            l = mid+1 ;
            for(int i=1;i<=n;i++) ans2[i].clear();
        }
    }

    cout << ans << "\n" ;
    for(int i=1;i<=n;i++){
        for(int x : ans2[i]){
            cout << x << " " ;
        }
        cout << "0\n" ;
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 37256 KB Memory limit exceeded
2 Runtime error 43 ms 37152 KB Memory limit exceeded
3 Runtime error 60 ms 37160 KB Memory limit exceeded
4 Runtime error 61 ms 37104 KB Memory limit exceeded
5 Runtime error 41 ms 37176 KB Memory limit exceeded
6 Runtime error 57 ms 37156 KB Memory limit exceeded
7 Runtime error 55 ms 37148 KB Memory limit exceeded
8 Runtime error 47 ms 37204 KB Memory limit exceeded
9 Runtime error 53 ms 37176 KB Memory limit exceeded
10 Runtime error 55 ms 37120 KB Memory limit exceeded
11 Runtime error 52 ms 37232 KB Memory limit exceeded
12 Incorrect 10 ms 4568 KB Output isn't correct
13 Incorrect 9 ms 4180 KB Output isn't correct
14 Incorrect 19 ms 5840 KB Output isn't correct
15 Incorrect 9 ms 4568 KB Output isn't correct
16 Incorrect 37 ms 8108 KB Output isn't correct
17 Incorrect 24 ms 6732 KB Output isn't correct
18 Incorrect 10 ms 4568 KB Output isn't correct
19 Incorrect 13 ms 4928 KB Output isn't correct
20 Incorrect 26 ms 6808 KB Output isn't correct