Submission #860648

#	Time	Username	Problem	Language	Result	Execution time	Memory
860648		agawron	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	195 ms	19488 KiB

jobs

#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 (stderr)

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