oj.uz

Submission #896238

# Submission time Handle Problem Language Result Execution time Memory
896238 2024-01-01T04:44:43 Z akkshaysr Job Scheduling (CEOI12_jobs) C++17
40 / 100
 177 ms 17124 KB 
#include <bits/stdc++.h>
#define fr first
#define se second
#define rep(i,a,b) for(int i = a; i < (b); ++i)
#define repr(i,a,b) for(int i = a; i > (b); --i)
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define IN(i,l,r) (l<i&&i<r)
#define pb push_back
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef long long ll;
const int U = 1e6+2;
int N,D,M;
pi job[U];
int jd[U/10 + 1];

bool check(int m){
    int day = 0,t = 0;
    while(day < N && t < M){
        ++day;
        t = min(t+m,jd[day]);
        if(t>M) t = M;
        if(job[t-1].fr + D < day){
            return false;
        }
    }
    return true;
}

int main(){
    cin.tie(0)->sync_with_stdio(false);
    cin >> N >> D >> M;
    rep(i,0,M){
        cin >> job[i].fr;
        jd[job[i].fr] += 1;
        job[i].se = i+1;
    }
    rep(i,2,N+1) jd[i] += jd[i-1];
    sort(job,job+M);
    int lo=1,hi=U;
    while(lo < hi){
        ll m = (lo+hi)/2;
        if(check(m)){
            hi = m;
        }else{
            lo = m+1;
        }
    }
    int day = 0,t = 0;
    cout << hi << '\n';
    while(day < N){
        ++day;
        int t_ = min(t+hi,jd[day]);
        rep(i,t,t_){
            cout << job[i].se << ' ';
        }
        cout << "0\n";
        t = t_;
    }
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3424 KB Output isn't correct
2 Incorrect 13 ms 3424 KB Output isn't correct
3 Incorrect 12 ms 3420 KB Output isn't correct
4 Incorrect 12 ms 3420 KB Output isn't correct
5 Incorrect 12 ms 3424 KB Output isn't correct
6 Incorrect 12 ms 3420 KB Output isn't correct
7 Incorrect 12 ms 3288 KB Output isn't correct
8 Incorrect 12 ms 3400 KB Output isn't correct
9 Correct 20 ms 3676 KB Output is correct
10 Correct 20 ms 3672 KB Output is correct
11 Correct 19 ms 3420 KB Output is correct
12 Correct 38 ms 4536 KB Output is correct
13 Incorrect 58 ms 7600 KB Output isn't correct
14 Correct 88 ms 8936 KB Output is correct
15 Incorrect 95 ms 11648 KB Output isn't correct
16 Correct 118 ms 13144 KB Output is correct
17 Incorrect 138 ms 14388 KB Output isn't correct
18 Correct 154 ms 14936 KB Output is correct
19 Correct 177 ms 17124 KB Output is correct
20 Incorrect 140 ms 14416 KB Output isn't correct