Submission #860679

#	Time	Username	Problem	Language	Result	Execution time	Memory
860679		agawron	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	279 ms	21228 KiB

jobs

#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

const int MAX_N = 1e5 + 5;

int n, d, m;
vector <int> p[MAX_N], ans[MAX_N];

bool check(int x){
    for(int i = 1; i <= n; i++) ans[i].clear();
    for(int i = 1, idx = 1 ; i <= n; idx = max(idx, ++i)){
        for(int id: p[i]){
            if(ans[idx].size() == x) idx++;
            if(idx > i + d) return 0;
            ans[idx].push_back(id);
        }
    }
    return 1;
}

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

    for(int i = 0; i < m; i++){
        int x;
        scanf("%d", &x);
        p[x].push_back(i + 1);
    }

    int lo = 1;
    int hi = m;
    int mi;

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

    check(lo);

    printf("%d\n", lo);

    for(int i = 1; i <= n; i++){
        for(int id: ans[i]){
            printf("%d ", id);
        }
        puts("0");
    }
}

Compilation message (stderr)

jobs.cpp: In function 'bool check(int)':
jobs.cpp:16:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |             if(ans[idx].size() == x) idx++;
      |                ~~~~~~~~~~~~~~~~^~~~
jobs.cpp: In function 'int main()':
jobs.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d %d %d", &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100