oj.uz

Submission #102158

# Submission time Handle Problem Language Result Execution time Memory
102158 2019-03-23T02:37:47 Z thebes Job Scheduling (CEOI12_jobs) C++14
30 / 100
 456 ms 20348 KB 
#include <bits/stdc++.h>
using namespace std;

const int MN = 1e5+5;
int N, D, M, i, x, lo, hi, src[10*MN];
vector<int> adj[MN];
queue<int> q;

bool check(int m){
    while(q.size()) q.pop();
    for(int i=1;i<=N;i++){
        for(auto v : adj[i]) q.push(v);
        int sz = min((int)q.size(), m);
        while(sz--){
            if(src[q.front()]+D-1<i) return 0;
            q.pop();
        }
    }
    return q.size()==0;
}

int main(){
    for(scanf("%d%d%d",&N,&D,&M),i=1;i<=M;i++)
        scanf("%d",&x), adj[x].push_back(i), src[i]=x;
    lo = 1, hi = M;
    while(lo<hi){
        int m = lo+hi>>1;
        if(check(m)) hi=m;
        else lo=m+1;
    }
    printf("%d\n",lo);
    while(q.size()) q.pop();
    for(i=1;i<=N;i++){
        for(auto v: adj[i]) q.push(v);
        int sz = min((int)q.size(), lo);
        while(sz--){
            printf("%d ",q.front());
            q.pop();
        }
        printf("0\n");
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:27:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = lo+hi>>1;
                 ~~^~~
jobs.cpp:23:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d%d%d",&N,&D,&M),i=1;i<=M;i++)
         ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
jobs.cpp:24:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x), adj[x].push_back(i), src[i]=x;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 4720 KB Output isn't correct
2 Incorrect 37 ms 4848 KB Output isn't correct
3 Incorrect 31 ms 4720 KB Output isn't correct
4 Incorrect 29 ms 4856 KB Output isn't correct
5 Incorrect 29 ms 4728 KB Output isn't correct
6 Incorrect 32 ms 4848 KB Output isn't correct
7 Incorrect 32 ms 4844 KB Output isn't correct
8 Incorrect 29 ms 4720 KB Output isn't correct
9 Incorrect 54 ms 4600 KB Output isn't correct
10 Incorrect 35 ms 4728 KB Output isn't correct
11 Correct 39 ms 4600 KB Output is correct
12 Incorrect 67 ms 6520 KB Output isn't correct
13 Correct 116 ms 9208 KB Output is correct
14 Incorrect 181 ms 11896 KB Output isn't correct
15 Incorrect 161 ms 12792 KB Output isn't correct
16 Correct 372 ms 15948 KB Output is correct
17 Correct 456 ms 18692 KB Output is correct
18 Correct 455 ms 18552 KB Output is correct
19 Incorrect 444 ms 20348 KB Output isn't correct
20 Correct 343 ms 18776 KB Output is correct