Submission #97851

#	Time	Username	Problem	Language	Result	Execution time	Memory
97851		RezwanArefin01	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	430 ms	20296 KiB

jobs

///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 1e5 + 10; 
vector<int> p[N], ans[N];
int n, d, m; 

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 = 1; i <= m; i++) {
        int x; scanf("%d", &x); 
        p[x].push_back(i);
    }
    int lo = 1, hi = m, idx; 
    while(lo <= hi) {
        int mid = lo + hi >> 1; 
        if(check(mid)) idx = mid, hi = mid - 1; 
        else lo = mid + 1; 
    }
    check(idx);
    printf("%d\n", idx); 
    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 between signed and unsigned integer expressions [-Wsign-compare]
             if(ans[idx].size() == x) ++idx; 
                ~~~~~~~~~~~~~~~~^~~~
jobs.cpp: In function 'int main()':
jobs.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lo + hi >> 1; 
                   ~~~^~~~
jobs.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &d, &m); 
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:26:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x; scanf("%d", &x); 
                ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100