oj.uz

Submission #896272

# Submission time Handle Problem Language Result Execution time Memory
896272 2024-01-01T07:17:30 Z akkshaysr Job Scheduling (CEOI12_jobs) C++17
100 / 100
 332 ms 28196 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];

pair<bool,vector<vi>> check(int m){
    vector<vi> s(N);
    int t=0;
    rep(day,1,N+1){
        rep(i,0,m){
            if(job[t].fr > day){
                break;
            }
            if(job[t].fr + D >= day){
                s[day-1].pb(job[t].se);
                ++t;
            }else{
                return {false,s};
            }
            if(t==M) return {true,s};
        }
    }
    cout << "over" << '\n';
    return {false,s};
}

int main(){
    cin.tie(0)->sync_with_stdio(false);
    cin >> N >> D >> M;
    rep(i,0,M){
        cin >> job[i].fr;
        job[i].se = i+1;
    }
    sort(job,job+M);
    int lo=1,hi=M;
    vector<vi> s;
    while(lo < hi){
        ll m = (lo+hi)/2;
        pair<bool,vector<vi>> res = check(m);
        if(res.fr){
            hi = m;
            s = res.se;
        }else{
            lo = m+1;
        }
    }
    cout << hi << '\n';
    for(auto &v:s){
        for(auto &e:v){
            cout << e << ' ';
        }
        cout << "0\n";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4884 KB Output is correct
2 Correct 27 ms 4880 KB Output is correct
3 Correct 22 ms 4884 KB Output is correct
4 Correct 22 ms 4868 KB Output is correct
5 Correct 22 ms 4884 KB Output is correct
6 Correct 24 ms 4896 KB Output is correct
7 Correct 23 ms 4884 KB Output is correct
8 Correct 22 ms 4880 KB Output is correct
9 Correct 50 ms 11568 KB Output is correct
10 Correct 61 ms 11684 KB Output is correct
11 Correct 29 ms 4668 KB Output is correct
12 Correct 59 ms 6232 KB Output is correct
13 Correct 83 ms 11268 KB Output is correct
14 Correct 148 ms 13048 KB Output is correct
15 Correct 149 ms 12484 KB Output is correct
16 Correct 210 ms 19248 KB Output is correct
17 Correct 233 ms 21448 KB Output is correct
18 Correct 256 ms 24964 KB Output is correct
19 Correct 332 ms 28196 KB Output is correct
20 Correct 241 ms 21384 KB Output is correct