oj.uz

Submission #742967

# Submission time Handle Problem Language Result Execution time Memory
742967 2023-05-17T07:03:56 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
9 / 100
 55 ms 25000 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 = 1e9 , 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
9.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 20748 KB Output isn't correct
2 Incorrect 37 ms 20868 KB Output isn't correct
3 Incorrect 34 ms 20816 KB Output isn't correct
4 Incorrect 31 ms 21568 KB Output isn't correct
5 Incorrect 37 ms 23020 KB Output isn't correct
6 Incorrect 40 ms 22144 KB Output isn't correct
7 Incorrect 31 ms 21748 KB Output isn't correct
8 Incorrect 29 ms 21056 KB Output isn't correct
9 Correct 45 ms 20804 KB Output is correct
10 Partially correct 55 ms 22452 KB Partially correct
11 Partially correct 54 ms 25000 KB Partially correct
12 Incorrect 9 ms 4436 KB Output isn't correct
13 Incorrect 7 ms 4188 KB Output isn't correct
14 Incorrect 16 ms 5460 KB Output isn't correct
15 Incorrect 9 ms 4436 KB Output isn't correct
16 Incorrect 26 ms 7120 KB Output isn't correct
17 Incorrect 20 ms 6224 KB Output isn't correct
18 Incorrect 9 ms 4564 KB Output isn't correct
19 Incorrect 12 ms 4824 KB Output isn't correct
20 Incorrect 20 ms 6224 KB Output isn't correct