oj.uz

Submission #1085547

# Submission time Handle Problem Language Result Execution time Memory
1085547 2024-09-08T11:54:34 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 290 ms 21396 KB 
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define int long long
#define ar array


const int N = 1e6 + 20;

int n, d, m;
ar<int, 2> A[N];

bool check(int x){
    int l = 0, r = 0;
    for(int i = 1;i <= n;i++){
        //cout<<l<<" "<<r<<'\n';
        while(r < m && A[r][0] == i)++r;
        if(l != r && l < m && i - A[l][0] > d)return 0;
        l = min(l + x, r);
    }
    return l == r && r== m;
}

void print(int x){
    int l = 0, r = 0;
    for(int i = 1;i <= n;i++){
        while(r < m && A[r][0] == i)++r;

        for(;l < min(l + x, r);l++){
            cout<<A[l][1]<<' ';
        }
        cout<<"0"<<endl;
        ++l;
    }
   
}

signed main() {ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n>>d>>m;
    for(int i = 0;i < m;i++){
        cin>>A[i][0];
        A[i][1] = 1 + i;
    }
    sort(A, A + m);
    int lo = 1, hi = m;
    int ans = m;
    //cout<<check(7);
    while(lo <= hi){
        //cout<<lo<<" "<<hi<<endl;
        int mid = (lo + hi) / 2;
        if(check(mid)){
            ans = mid;
            hi = mid - 1;
        }else lo = mid + 1;
    }
    cout<<ans<<endl;
    print(ans);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3160 KB Output is correct
2 Correct 23 ms 3164 KB Output is correct
3 Correct 23 ms 3164 KB Output is correct
4 Correct 24 ms 3088 KB Output is correct
5 Correct 22 ms 3160 KB Output is correct
6 Correct 22 ms 3164 KB Output is correct
7 Correct 23 ms 3160 KB Output is correct
8 Correct 23 ms 3164 KB Output is correct
9 Correct 137 ms 3668 KB Output is correct
10 Correct 115 ms 3456 KB Output is correct
11 Correct 20 ms 3152 KB Output is correct
12 Correct 40 ms 5968 KB Output is correct
13 Correct 66 ms 8532 KB Output is correct
14 Correct 101 ms 9296 KB Output is correct
15 Correct 110 ms 12112 KB Output is correct
16 Correct 135 ms 14732 KB Output is correct
17 Correct 160 ms 17488 KB Output is correct
18 Correct 173 ms 20308 KB Output is correct
19 Correct 290 ms 21396 KB Output is correct
20 Correct 156 ms 17532 KB Output is correct