Submission #41290

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
41290	2018-02-15T16:29:35 Z	evpipis	Job Scheduling (CEOI12_jobs)	C++	100 / 100	354 ms	14692 KB

jobs

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef pair<int, int> ii;

const int len = 1e6+5;
int n, d, m;
ii a[len];

bool check(int x){
    int po = 0;
    for (int i = 1; i <= n+1; i++){
        int temp = x;
        while (po < m && temp-- && a[po].fi <= i){
            if (i > d+a[po].fi) return false;
            po++;
        }
    }
    return true;
}

int bs(){
    int l = 1, r = m, ans;
    while (l <= r){
        int mid = (l+r)/2;
        if (check(mid)){
            ans = mid;
            r = mid-1;
        }
        else
            l = mid+1;
    }

    return ans;
}

int main(){
    scanf("%d %d %d", &n, &d, &m);
    for (int i = 0; i < m; i++){
        scanf("%d", &a[i].fi);
        a[i].se = i+1;
    }
    sort(a, a+m);

    int x = bs();
    printf("%d\n", x);

    int po = 0;
    for (int i = 1; i <= n; i++){
        int temp = x;
        while (po < m && temp-- && a[po].fi <= i){
            printf("%d ", a[po].se);
            po++;
        }
        printf("0\n");
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:40:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &d, &m);
                                  ^
jobs.cpp:42:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i].fi);
                              ^
jobs.cpp: In function 'int bs()':
jobs.cpp:36:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ans;
            ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	8700 KB	Output is correct
2	Correct	32 ms	8868 KB	Output is correct
3	Correct	32 ms	8904 KB	Output is correct
4	Correct	31 ms	8940 KB	Output is correct
5	Correct	33 ms	8940 KB	Output is correct
6	Correct	44 ms	8940 KB	Output is correct
7	Correct	35 ms	9028 KB	Output is correct
8	Correct	33 ms	9028 KB	Output is correct
9	Correct	51 ms	9172 KB	Output is correct
10	Correct	44 ms	9172 KB	Output is correct
11	Correct	42 ms	9172 KB	Output is correct
12	Correct	79 ms	9556 KB	Output is correct
13	Correct	115 ms	10324 KB	Output is correct
14	Correct	162 ms	11044 KB	Output is correct
15	Correct	193 ms	11804 KB	Output is correct
16	Correct	239 ms	12572 KB	Output is correct
17	Correct	278 ms	13088 KB	Output is correct
18	Correct	302 ms	13980 KB	Output is correct
19	Correct	354 ms	14692 KB	Output is correct
20	Correct	284 ms	14692 KB	Output is correct