oj.uz

Submission #860675

# Submission time Handle Problem Language Result Execution time Memory
860675 2023-10-13T16:59:36 Z agawron Job Scheduling (CEOI12_jobs) C++14
10 / 100
 225 ms 20280 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 = 1e6;
    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++;
        }
    }
    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));
        }
        puts("0");
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 5716 KB Output isn't correct
2 Incorrect 28 ms 5720 KB Output isn't correct
3 Incorrect 28 ms 5600 KB Output isn't correct
4 Incorrect 28 ms 5716 KB Output isn't correct
5 Incorrect 29 ms 5716 KB Output isn't correct
6 Incorrect 28 ms 5716 KB Output isn't correct
7 Incorrect 33 ms 5740 KB Output isn't correct
8 Incorrect 29 ms 5720 KB Output isn't correct
9 Correct 37 ms 5972 KB Output is correct
10 Correct 38 ms 5968 KB Output is correct
11 Incorrect 24 ms 5236 KB Output isn't correct
12 Incorrect 39 ms 4700 KB Output isn't correct
13 Incorrect 64 ms 7516 KB Output isn't correct
14 Incorrect 84 ms 8044 KB Output isn't correct
15 Incorrect 106 ms 10848 KB Output isn't correct
16 Incorrect 148 ms 15440 KB Output isn't correct
17 Incorrect 168 ms 14176 KB Output isn't correct
18 Incorrect 193 ms 19040 KB Output isn't correct
19 Incorrect 225 ms 20280 KB Output isn't correct
20 Incorrect 154 ms 14160 KB Output isn't correct