oj.uz

Submission #374673

# Submission time Handle Problem Language Result Execution time Memory
374673 2021-03-07T20:22:24 Z ritul_kr_singh Job Scheduling (CEOI12_jobs) C++17
55 / 100
 403 ms 17388 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define sp << " " <<
#define nl << "\n"

int n, d, m;
array<int, 2> a[1000000];

bool possible(int k){
    for(int i=0; i<m; ++i){
        int best = ((i+1)+k-1)/k;
        if(best>a[i][0]+d) return false;
    }
    return true;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> d >> m;
    for(int i=0; i<m; ++i) cin >> a[i][0], a[i][1] = i;
    sort(a, a+m);
    int low = 1, high = m;
    while(low<high){
        int mid = (low+high)/2;
        if(possible(mid)) high = mid;
        else low = mid+1;
    }
    cout << low nl;
    int j=0;
    for(int i=0; i<n; ++i){
        int curr=0;
        while(curr+1<=low and j<m and a[j][0]<=i+1){
            cout << a[j][1]+1 << ' ';
            ++j;
            ++curr;
        }
        cout << 0 nl;
    }
}

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 2028 KB Output isn't correct
2 Incorrect 34 ms 2284 KB Output isn't correct
3 Incorrect 33 ms 2028 KB Output isn't correct
4 Incorrect 35 ms 2028 KB Output isn't correct
5 Incorrect 33 ms 2028 KB Output isn't correct
6 Incorrect 33 ms 2028 KB Output isn't correct
7 Incorrect 33 ms 2028 KB Output isn't correct
8 Incorrect 33 ms 2028 KB Output isn't correct
9 Correct 46 ms 2156 KB Output is correct
10 Correct 48 ms 2156 KB Output is correct
11 Correct 41 ms 2096 KB Output is correct
12 Correct 83 ms 3948 KB Output is correct
13 Correct 125 ms 5996 KB Output is correct
14 Correct 172 ms 8172 KB Output is correct
15 Incorrect 211 ms 8300 KB Output isn't correct
16 Correct 249 ms 9836 KB Output is correct
17 Correct 299 ms 14080 KB Output is correct
18 Correct 350 ms 15212 KB Output is correct
19 Correct 403 ms 17388 KB Output is correct
20 Correct 300 ms 14060 KB Output is correct