oj.uz

Submission #744507

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

bool isok(int k) {
    int indexi=0;
    int indexj=0;
    for(int 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;
}
int bsearch() {
    int a=1,b=1e7;
    unordered_map<int,bool> m;
    while(a<=b) {
        int 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(int i=0;i<M;i++) {
        cin>>v[i].first;
        v[i].second=i;
    }
    sort(v.begin(), v.end());
    int sol=bsearch();
    cout<<bsearch()<<"\n";
    int indexi=0;
    int indexj=0;
    for(int 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 35 ms 1612 KB Output isn't correct
2 Incorrect 50 ms 1640 KB Output isn't correct
3 Incorrect 37 ms 1620 KB Output isn't correct
4 Incorrect 53 ms 1604 KB Output isn't correct
5 Incorrect 38 ms 1612 KB Output isn't correct
6 Incorrect 34 ms 1612 KB Output isn't correct
7 Incorrect 35 ms 1636 KB Output isn't correct
8 Incorrect 35 ms 1600 KB Output isn't correct
9 Correct 45 ms 1860 KB Output is correct
10 Correct 50 ms 1820 KB Output is correct
11 Correct 43 ms 1596 KB Output is correct
12 Correct 85 ms 3136 KB Output is correct
13 Correct 166 ms 4572 KB Output is correct
14 Correct 185 ms 6112 KB Output is correct
15 Correct 209 ms 7536 KB Output is correct
16 Correct 280 ms 9084 KB Output is correct
17 Correct 328 ms 10508 KB Output is correct
18 Correct 348 ms 12060 KB Output is correct
19 Correct 399 ms 13788 KB Output is correct
20 Correct 319 ms 10576 KB Output is correct