oj.uz

답안 #744504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
744504 2023-05-18T15:53:26 Z alecurse Job Scheduling (CEOI12_jobs) C++14
60 / 100
 387 ms 13736 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
60.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 37 ms 1592 KB Output isn't correct
2 Incorrect 33 ms 1608 KB Output isn't correct
3 Incorrect 34 ms 1596 KB Output isn't correct
4 Incorrect 32 ms 1588 KB Output isn't correct
5 Incorrect 31 ms 1600 KB Output isn't correct
6 Incorrect 33 ms 1600 KB Output isn't correct
7 Incorrect 33 ms 1596 KB Output isn't correct
8 Incorrect 32 ms 1580 KB Output isn't correct
9 Correct 44 ms 1800 KB Output is correct
10 Correct 42 ms 1848 KB Output is correct
11 Correct 44 ms 1600 KB Output is correct
12 Correct 89 ms 3144 KB Output is correct
13 Correct 124 ms 4572 KB Output is correct
14 Correct 186 ms 6120 KB Output is correct
15 Correct 199 ms 7544 KB Output is correct
16 Correct 280 ms 9056 KB Output is correct
17 Correct 336 ms 10528 KB Output is correct
18 Correct 341 ms 12068 KB Output is correct
19 Correct 387 ms 13736 KB Output is correct
20 Correct 311 ms 10512 KB Output is correct