oj.uz

Submission #744508

# Submission time Handle Problem Language Result Execution time Memory
744508 2023-05-18T15:56:51 Z alecurse Job Scheduling (CEOI12_jobs) C++14
60 / 100
 381 ms 20704 KB 
#include <iostream>
#include <vector>
#define mp make_pair
#include <unordered_map>
#define ll long long int
#include <algorithm>
using namespace std;
ll N,D,M;
vector<pair<ll,ll> > v;

bool isok(ll k) {
    ll indexi=0;
    ll indexj=0;
    for(ll i=0;i<M;i++) {
        if(indexj==k||v[i].first>indexi+1) {
            indexi++;
            indexj=0;
            if(indexi>=N) return false;
        }   
        if(indexi+1-v[i].first>D) return false;
        indexj++;
    }
    return true;
}
ll bsearch() {
    ll a=1,b=1e7;
    unordered_map<ll,bool> m;
    while(a<=b) {
        ll k=(a+b)/2;
        m[k]=isok(k);
        if(m[k]&&(k==1||(m.count(k-1)&&!m[k-1]))) return k;
        if(!m[k]&&m.count(k+1)&&m[k+1]) return k+1;
        if(m[k]) b=k-1;
        else a=k+1;
    }
    return -1;
}


int main() {
    cin>>N>>D>>M;
    v.resize(M);
    for(ll i=0;i<M;i++) {
        cin>>v[i].first;
        v[i].second=i;
    }
    sort(v.begin(), v.end());
    ll sol=bsearch();
    cout<<bsearch()<<"\n";
    ll indexi=0;
    ll indexj=0;
    for(ll i=0;i<M;i++) {
        if(indexj==sol||v[i].first>indexi+1) {
            indexi++;
            indexj=0;
            cout<<0<<"\n";
        }   
        cout<<v[i].second+1<<" ";
        indexj++;
    }
    cout<<0<<'\n';
    while(indexi<N-1) {
        indexi++;
        cout<<0<<"\n";
    }
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 2380 KB Output isn't correct
2 Incorrect 33 ms 2364 KB Output isn't correct
3 Incorrect 44 ms 2368 KB Output isn't correct
4 Incorrect 45 ms 2376 KB Output isn't correct
5 Incorrect 34 ms 2384 KB Output isn't correct
6 Incorrect 34 ms 2432 KB Output isn't correct
7 Incorrect 39 ms 2392 KB Output isn't correct
8 Incorrect 33 ms 2376 KB Output isn't correct
9 Correct 45 ms 2544 KB Output is correct
10 Correct 46 ms 2636 KB Output is correct
11 Correct 44 ms 2380 KB Output is correct
12 Correct 89 ms 4636 KB Output is correct
13 Correct 125 ms 6956 KB Output is correct
14 Correct 191 ms 9240 KB Output is correct
15 Correct 220 ms 11448 KB Output is correct
16 Correct 285 ms 13776 KB Output is correct
17 Correct 317 ms 15968 KB Output is correct
18 Correct 352 ms 18320 KB Output is correct
19 Correct 381 ms 20704 KB Output is correct
20 Correct 325 ms 15992 KB Output is correct