oj.uz

Submission #424778

# Submission time Handle Problem Language Result Execution time Memory
424778 2021-06-12T10:03:55 Z aris12345678 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 329 ms 17244 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN = 100005;
const int mxM = 1000005;
pair<int, int> day[mxM];

bool check(int x, int m, int d, int n) {
    int j = 0;
    for(int i = 1; i <= n+1; i++) {
        int md = x;
        while(md-- && j < m && day[j].first <= i) {
            if(i > d+day[j].first)
                return false;
            j++;
        }
    }
    return true;
}

int main() {
    int n, d, m;
    scanf("%d %d %d", &n, &d, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d", &day[i].first);
        day[i].second = i+1;
    }
    sort(day, day+m);
    int lb = 1, rb = m, md, ans = -1;
    while(lb <= rb) {
        md = (lb+rb)/2;
        if(check(md, m, d, n)) {
            ans = md;
            rb = md-1;
        } else
            lb = md+1;
    }
    printf("%d\n", ans);
    int j = 0;
    for(int i = 1; i <= n; i++) {
        int x = ans;
        while(x-- && j < m && day[j].first <= i) {
            printf("%d ", day[j].second);
            j++;
        }
        printf("0\n");
    }
    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d %d %d", &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf("%d", &day[i].first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1860 KB Output is correct
2 Correct 26 ms 1884 KB Output is correct
3 Correct 25 ms 1908 KB Output is correct
4 Correct 25 ms 1896 KB Output is correct
5 Correct 25 ms 1860 KB Output is correct
6 Correct 33 ms 1868 KB Output is correct
7 Correct 31 ms 1880 KB Output is correct
8 Correct 25 ms 1860 KB Output is correct
9 Correct 39 ms 2096 KB Output is correct
10 Correct 39 ms 2116 KB Output is correct
11 Correct 34 ms 1988 KB Output is correct
12 Correct 68 ms 3880 KB Output is correct
13 Correct 104 ms 5744 KB Output is correct
14 Correct 153 ms 8008 KB Output is correct
15 Correct 170 ms 9392 KB Output is correct
16 Correct 238 ms 11884 KB Output is correct
17 Correct 252 ms 13928 KB Output is correct
18 Correct 302 ms 15040 KB Output is correct
19 Correct 329 ms 17244 KB Output is correct
20 Correct 254 ms 13832 KB Output is correct