oj.uz

Submission #744499

# Submission time Handle Problem Language Result Execution time Memory
744499 2023-05-18T15:51:16 Z alecurse Job Scheduling (CEOI12_jobs) C++14
30 / 100
 387 ms 13728 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=2*1e5;
    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
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 1592 KB Output isn't correct
2 Incorrect 36 ms 1600 KB Output isn't correct
3 Incorrect 37 ms 1592 KB Output isn't correct
4 Incorrect 37 ms 1644 KB Output isn't correct
5 Incorrect 44 ms 1596 KB Output isn't correct
6 Incorrect 35 ms 1604 KB Output isn't correct
7 Incorrect 46 ms 1612 KB Output isn't correct
8 Incorrect 34 ms 1592 KB Output isn't correct
9 Incorrect 49 ms 1816 KB Output isn't correct
10 Incorrect 49 ms 1856 KB Output isn't correct
11 Correct 43 ms 1540 KB Output is correct
12 Incorrect 104 ms 3052 KB Output isn't correct
13 Correct 139 ms 4636 KB Output is correct
14 Incorrect 205 ms 6124 KB Output isn't correct
15 Incorrect 233 ms 7536 KB Output isn't correct
16 Correct 308 ms 9076 KB Output is correct
17 Correct 317 ms 10508 KB Output is correct
18 Correct 369 ms 12060 KB Output is correct
19 Incorrect 387 ms 13728 KB Output isn't correct
20 Correct 364 ms 10600 KB Output is correct