oj.uz

Submission #860648

# Submission time Handle Problem Language Result Execution time Memory
860648 2023-10-13T15:27:03 Z agawron Job Scheduling (CEOI12_jobs) C++14
0 / 100
 195 ms 19488 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){
//                cout << "a r d i " << a[r] << ' ' << d << ' ' << i << '\n';
                return 0;
            }
            else r++;
        }
//        cout << "---" << '\n';
//        cout << "x r l " << x << ' ' << r << ' ' << l << '\n';
    }
    return r >= n;
}

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);

//    cout << "---" << '\n';
//
//    for(int i = 1; i <= m; i++){
//        printf("%d ", a[i].first);
//    }
//
//    cout << '\n' << "---" << '\n';

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

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 5596 KB Output isn't correct
2 Incorrect 14 ms 5780 KB Output isn't correct
3 Incorrect 14 ms 5728 KB Output isn't correct
4 Incorrect 15 ms 5600 KB Output isn't correct
5 Incorrect 15 ms 5780 KB Output isn't correct
6 Incorrect 15 ms 5764 KB Output isn't correct
7 Incorrect 15 ms 5724 KB Output isn't correct
8 Incorrect 14 ms 5724 KB Output isn't correct
9 Incorrect 40 ms 9056 KB Output isn't correct
10 Incorrect 37 ms 9076 KB Output isn't correct
11 Incorrect 16 ms 4952 KB Output isn't correct
12 Incorrect 33 ms 5452 KB Output isn't correct
13 Incorrect 55 ms 7844 KB Output isn't correct
14 Incorrect 71 ms 8892 KB Output isn't correct
15 Incorrect 79 ms 7984 KB Output isn't correct
16 Incorrect 116 ms 11332 KB Output isn't correct
17 Incorrect 125 ms 11224 KB Output isn't correct
18 Incorrect 146 ms 11276 KB Output isn't correct
19 Incorrect 195 ms 19488 KB Output isn't correct
20 Incorrect 115 ms 11128 KB Output isn't correct