oj.uz

Submission #896121

# Submission time Handle Problem Language Result Execution time Memory
896121 2023-12-31T20:42:05 Z akkshaysr Job Scheduling (CEOI12_jobs) C++17
0 / 100
 182 ms 17052 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){
        ++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=0,hi=U;
    while(lo < hi){
        ll m = (lo+hi)/2;
        if(check(m)){
            hi = m;
        }else{
            lo = m+1;
        }
    }
    int day = 0,t = 0;
    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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 3680 KB Output isn't correct
2 Incorrect 11 ms 3420 KB Output isn't correct
3 Incorrect 11 ms 3416 KB Output isn't correct
4 Incorrect 12 ms 3416 KB Output isn't correct
5 Incorrect 13 ms 3420 KB Output isn't correct
6 Incorrect 11 ms 3420 KB Output isn't correct
7 Incorrect 17 ms 3420 KB Output isn't correct
8 Incorrect 13 ms 3420 KB Output isn't correct
9 Incorrect 22 ms 3664 KB Expected EOLN
10 Incorrect 20 ms 3616 KB Expected EOLN
11 Incorrect 19 ms 3420 KB Expected EOLN
12 Incorrect 39 ms 4536 KB Expected EOLN
13 Incorrect 57 ms 7504 KB Expected EOLN
14 Incorrect 80 ms 8784 KB Expected EOLN
15 Incorrect 97 ms 11604 KB Expected EOLN
16 Incorrect 130 ms 13136 KB Expected EOLN
17 Incorrect 139 ms 14420 KB Expected EOLN
18 Incorrect 157 ms 14948 KB Expected EOLN
19 Incorrect 182 ms 17052 KB Expected EOLN
20 Incorrect 142 ms 14172 KB Expected EOLN