oj.uz

Submission #1085542

# Submission time Handle Problem Language Result Execution time Memory
1085542 2024-09-08T11:51:01 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 195 ms 21328 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 \n";
        ++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<<'\n';
    print(ans);
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 3160 KB Expected EOLN
2 Incorrect 14 ms 3160 KB Expected EOLN
3 Incorrect 14 ms 3164 KB Expected EOLN
4 Incorrect 14 ms 3164 KB Expected EOLN
5 Incorrect 14 ms 3164 KB Expected EOLN
6 Incorrect 14 ms 3164 KB Expected EOLN
7 Incorrect 15 ms 3164 KB Expected EOLN
8 Incorrect 16 ms 3164 KB Expected EOLN
9 Incorrect 24 ms 3464 KB Expected EOLN
10 Incorrect 27 ms 3452 KB Expected EOLN
11 Incorrect 24 ms 3100 KB Expected EOLN
12 Incorrect 41 ms 5972 KB Expected EOLN
13 Incorrect 71 ms 8576 KB Expected EOLN
14 Incorrect 85 ms 9296 KB Expected EOLN
15 Incorrect 107 ms 12112 KB Expected EOLN
16 Incorrect 134 ms 14716 KB Expected EOLN
17 Incorrect 152 ms 17488 KB Expected EOLN
18 Incorrect 178 ms 20352 KB Expected EOLN
19 Incorrect 195 ms 21328 KB Expected EOLN
20 Incorrect 150 ms 17540 KB Expected EOLN