oj.uz

답안 #743984

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743984 2023-05-18T06:58:55 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
55 / 100
 44 ms 15788 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) day = S[i].first ;
        if(day <= S[i].first + d){ // do job i-th
            cnt++ ;
            ans2[day].push_back(S[i].second) ;
        }
        else {
            return false ;
        }
        if(cnt == mid){
            day++;
            cnt = 0 ;
        }
    }

    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 = m , 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
55.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 6228 KB Output is correct
2 Correct 21 ms 6228 KB Output is correct
3 Correct 21 ms 6228 KB Output is correct
4 Correct 22 ms 6228 KB Output is correct
5 Correct 22 ms 6228 KB Output is correct
6 Correct 23 ms 6144 KB Output is correct
7 Correct 23 ms 6116 KB Output is correct
8 Correct 22 ms 6228 KB Output is correct
9 Correct 34 ms 9620 KB Output is correct
10 Correct 38 ms 9052 KB Output is correct
11 Correct 44 ms 15788 KB Output is correct
12 Incorrect 9 ms 4472 KB Output isn't correct
13 Incorrect 10 ms 4500 KB Output isn't correct
14 Incorrect 12 ms 4692 KB Output isn't correct
15 Incorrect 9 ms 4596 KB Output isn't correct
16 Incorrect 11 ms 5452 KB Output isn't correct
17 Incorrect 11 ms 4716 KB Output isn't correct
18 Incorrect 10 ms 4552 KB Output isn't correct
19 Incorrect 8 ms 4564 KB Output isn't correct
20 Incorrect 14 ms 4712 KB Output isn't correct