oj.uz

Submission #860674

# Submission time Handle Problem Language Result Execution time Memory
860674 2023-10-13T16:58:14 Z agawron Job Scheduling (CEOI12_jobs) C++14
0 / 100
 232 ms 23496 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++;
        }
        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 30 ms 5968 KB Output isn't correct
2 Incorrect 30 ms 6056 KB Output isn't correct
3 Incorrect 30 ms 5968 KB Output isn't correct
4 Incorrect 30 ms 5980 KB Output isn't correct
5 Incorrect 30 ms 5968 KB Output isn't correct
6 Incorrect 30 ms 5980 KB Output isn't correct
7 Incorrect 30 ms 5980 KB Output isn't correct
8 Incorrect 30 ms 5976 KB Output isn't correct
9 Incorrect 47 ms 9056 KB Expected EOLN
10 Incorrect 50 ms 9044 KB Expected EOLN
11 Incorrect 24 ms 5204 KB Output isn't correct
12 Incorrect 40 ms 4700 KB Output isn't correct
13 Incorrect 58 ms 7528 KB Output isn't correct
14 Incorrect 84 ms 8020 KB Output isn't correct
15 Incorrect 108 ms 10844 KB Output isn't correct
16 Incorrect 151 ms 15472 KB Output isn't correct
17 Incorrect 161 ms 14184 KB Output isn't correct
18 Incorrect 196 ms 19304 KB Output isn't correct
19 Incorrect 232 ms 23496 KB Output isn't correct
20 Incorrect 157 ms 14160 KB Output isn't correct