Submission #565309

#	Time	Username	Problem	Language	Result	Execution time	Memory
565309		PranjalChandra	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	340 ms	20412 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 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:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         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]
   24 |     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]
   26 |         int x; scanf("%d", &x);
      |                ~~~~~^~~~~~~~~~

• Subtask 1: 100 / 100