oj.uz

Submission #860668

# Submission time Handle Problem Language Result Execution time Memory
860668 2023-10-13T16:43:48 Z agawron Job Scheduling (CEOI12_jobs) C++14
0 / 100
 197 ms 18256 KB 
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

const int MAX_M = 1e6 + 5;
const int MAX_N = 1e5 + 5;

int n, d, m;
pair <int, int> a[MAX_M];
vector <int> ans[MAX_N];

bool check(int x){
    int r = 1;

    for(int i = 1; i <= n; i++){
        int l = r;
        while(a[r].first <= i && r - l < x){
            if(a[r].first + d < i && r <= n){
                return 0;
            }
            else r++;
        }
    }
    return 1;
}

int main(){
    scanf("%d %d %d", &n, &d, &m);

    for(int i = 1; i <= m; i++){
        scanf("%d", &a[i].first);
        a[i].second = i;
    }

    sort(a + 1, a + m + 1);

    int lo = 1;
    int hi = 5;
    int mi;

    while(lo < hi){
        mi = (lo + hi)/2;
        if(check(mi)) hi = mi;
        else lo = mi + 1;
    }

    int r = 1;

    for(int i = 1; i <= n; i++){
        int l = r;
        while(a[r].first <= i && r - l < lo && r <= m){
            ans[i].push_back(a[r].second);
            r++;
        }
        ans[i].push_back(0);
    }
    printf("%d\n", lo);

    for(int i = 1; i <= n; i++){
        for(int j = 0; j < ans[i].size(); j++){
            printf("%d ", ans[i].at(j));
        }
        printf("\n");
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 0; j < ans[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
jobs.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d %d %d", &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf("%d", &a[i].first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 5464 KB Output isn't correct
2 Incorrect 14 ms 5468 KB Output isn't correct
3 Incorrect 14 ms 5480 KB Output isn't correct
4 Incorrect 14 ms 5468 KB Output isn't correct
5 Incorrect 14 ms 5468 KB Output isn't correct
6 Incorrect 14 ms 5468 KB Output isn't correct
7 Incorrect 14 ms 5468 KB Output isn't correct
8 Incorrect 14 ms 5468 KB Output isn't correct
9 Incorrect 37 ms 8796 KB Output isn't correct
10 Incorrect 36 ms 8784 KB Output isn't correct
11 Incorrect 15 ms 4700 KB Output isn't correct
12 Incorrect 31 ms 4704 KB Output isn't correct
13 Incorrect 45 ms 6744 KB Output isn't correct
14 Incorrect 68 ms 7508 KB Output isn't correct
15 Incorrect 75 ms 6748 KB Output isn't correct
16 Incorrect 99 ms 9564 KB Output isn't correct
17 Incorrect 115 ms 9568 KB Output isn't correct
18 Incorrect 131 ms 9808 KB Output isn't correct
19 Incorrect 197 ms 18256 KB Output isn't correct
20 Incorrect 115 ms 9556 KB Output isn't correct